글 읽기 - 회의실 배정 문제, 맞긴했으나 의문점이 있습니다

gidskql6671 5년 전 1

아래의 소스 코드에서 주석처리된 부분을 포함하면 정답이 나오고, 주석처리된 부분을 포함하지 않으면 오답이 나옵니다.

그리디 알고리즘을 이용하여 풀었는데, 끝나는 시점을 오름차순으로 정렬하면, 더 먼저 만나는 원소가 더 빨리 or 같이 끝난다는 뜻이니깐

시작시간은 어떻게 되든, 이전 회의가 끝나는 시간 뒤에만 있다면 상관이 없지 않나요??

끝나는 시간이 같을 경우, 시작 시간 순으로 오름차순 정렬하는 것이 무슨 의미가 있는지 궁금합니다...

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> v;

struct mycomp {
	bool operator()(const pair<int, int> &a, const pair<int, int> &b) const {
		/*if (a.second == b.second) 
			return a.first < b.first; */
		return a.second < b.second;
	}
};

int main() {
	int n, Count = 0, end, tmp1, tmp2;

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		v.push_back(make_pair(tmp1, tmp2));
	}
	sort(v.begin(), v.end(), mycomp());

	Count++; end = v[0].second;
	for (int i = 1; i < n; i++) {
		if (v[i].first >= end) {
			end = v[i].second;
			Count++;
		}
	}

	printf("%d\n", Count);

	return 0;
}

yoonsang9114 5년 전 0

회의가 시작하자마자 끝나는 경우 문제가 발생할거 같아요.

gidskql6671 5년 전 0

그 경우는 아닐겁니다. 하단의 for문에서 시작 시간이 이전 회의가 끝나는 시간과 동일할 때도 카운트를 해주기 때문에, 모두 포함이 되는 것을 확인하였습니다...

또한, 끝나는 시간 순으로 오름차순이 되어있어서 시작시간이 a이고 끝시간 b인 다른 회의가 먼저 있었다 할지라도, 시작시간 끝시간 둘다 b인 회의 or 시작시간 끝시간 둘다 a인 회의는 카운트되니깐요...

yoonsang9114 5년 전 11

시작 시간순으로 정렬이 되어있지 않다고 할 때, 회의 A가 (K,K)이고, 회의 B가(N,K)(N<K) 라고 할 때 회의 A가 먼저 진행되면 회의 B->A를 진행할 수 있었음에도 회의 A만 진행하게 되지 않을까요?

이중 정렬을 묻는게 이 문제의 의도였다면 크기를 가지지 않는 경계값에 관해서 더 설명이 필요하지 않을까 싶습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

회의실 배정 문제, 맞긴했으나 의문점이 있습니다

gidskql6671 5년 전 1

yoonsang9114 5년 전 0

gidskql6671 5년 전 0

yoonsang9114 5년 전 11

gidskql6671 5년 전 0

97mjh1012 4년 전 0

hyunseungbb 3년 전 0

chldntjr1211 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말