BOJ 11000 - 강의실 배정

유명한 그리디의 스케줄링 문제이다.

 

발상이 떠오르지 않는다면 어려울 수 있는 그리디 문제이다. 그러나 한번 알아두면 평생 쓴다!

 

어떤 방법으로 강의들을 배정해야 최소한으로 필요한 강의실을 개수를 구할 수 있을까?

 

순서대로 계획을 짜보자

 

1. 빨리 시작하는 순으로 배정한다.

시작이 빠른 강의가 가장 늦게 끝나는 경우가 있음으로 사용하기 어렵다.

 

2. 강의 시간이 짧은 순서대로 배정한다.

강의 시간이 짧은 강의가 제일 나중에 나오게 되면 비효율적이다.

 

3. 적게 겹치는 강의부터 배정한다.

이 역시 쉽게 반례를 찾을 수 있다.

 

4. 빨리 끝나는 순으로 배정한다.

뭔 짓을 해도 반례를 찾을 수 없다.

 

전략이 나왔다. 빨리 끝나는 순으로 강의를 배정시켜 보자.

 

이는 우선순위큐를 이용해 배정할 수 있다. 빠른 순으로 넣고 우선순위큐의 top의 강의가 끝나는 시간과 현재 보는 강의의 시간이 겹치면 우선순위큐에 넣고, 그렇지 않다면 top의 끝나는 시간을 수정하는 식으로 구성하면 된다.

int main() {
	int n;
	cin >> n;
	int ans = 0;
	priority_queue<int, vector<int>, greater<int>>pq;
	vector<pair<int, int>>arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	sort(arr.begin(), arr.end());
	pq.push(arr[0].second);
	for (int i = 1; i < n; i++) {
		pq.push(arr[i].second);
		if (pq.top() <= arr[i].first) {
			pq.pop();
		}
	}
	ans = pq.size();
	cout << ans;
	return 0;
}

 

4번의 전략이 왜 성립할까?

4번 전략으로 찾은 답이 최적이 아니라고 가정해 보자. 이때 4번 전략으로 해를 찾을 때 최적의 해와 n번째까지는 결과가 같다면 최적의 해에서 n+1번째 해까지 4번 전략과 똑같이 만들어낼수 있다. 이러한 해가 여전히 최적이라면 4번전략과 n+1까지 같게 되는 것이다. 따라서 n번째 까지 같다는 가정에 모순됨으로 성립한다.

 

interval scheduling의 한 문제인 강의실 배정은 매우 유익한 문제이다! 한번 7888번도 풀어보기를 추천한다.