백준 11000번 강의실 배정 (C++)

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

이전에 풀었던 BOJ문제 공주님의 정원 문제와 비슷하다고 하여 풀어봤다. 공주님 문제를 어렵게 느꼈고 깨달은 것이 많은 문제여서 비장한(?) 마음으로 임했다.

 

먼저 최대한 수업시간들이 이어져있도록 꼬리물기를 시켜야한다. 그러므로 한 수업이 끝나고 다음 수업들의 수업을 스캔하는 과정이 필요하다. 

 

1 2

1 2

2 7

2 4

3 7

이라고 가정하자. 그렇다면 먼저 1~2 수업을 할 것이다. 그리고 다음 수업시간의 시작 시간과 이전 수업 시간의 끝나는 시간을 비교하자.

그럼 1, 2는 같은 시간이므로 불가능하다. 그러므로 강의실을 하나 추가한다. 다음으로 2~ 7 수업이 가능하다.

3번쨰 까지 탐색한 후 상황을 보면 다음과 같다. 

1번 강의실 : 1~2, 2~7

2번 강의실 : 1~2

 

4번째를 보면 2~4 이므로 2번 강의실에 들어갈 수 있다.

1번 강의실 : 1~2, 2~7

2번 강의실 : 1~2, 2~4

5번째는 강의실을 하나 추가하여 정답은 3개이다.

 

이제 이것을 코드로 옮겨야하는데, 만약 생각처럼 1번당 스캔하게 되면 O(N*N)이 되어 20만 * 20만 = 40억 이므로 TLE이다. 여기서 필요한 것은 우선순위 큐이다.

 

먼저 우선순위큐로 시작하는 시간을 기준으로 가장 빨리 시작하는 것 부터 꺼낸다. 

그리고 끝나는 시간들을 보관할 우선순위큐를 하나 더 선언한다.

 

여기서 눈치채야하는 것은, 모든 강의실을 살펴볼 필요가 없다.

 

예를들어, 현재 끝나는시간 우선순위큐 상태가 4 , 5, 7 ,8 ,11 이라하자. 그리고 지금 보는 수업이 5~8 라면 5보다 작거나 같은 끝나는 시간이 있는지 따져봐야한다. 그렇다면 끝나는 시간 우선순위큐의 최소값만 보면 된다. 만약 최소값보다 5가 작다면 다음 시간은 볼 필요도 없다. 

그렇다면  위 상황에서 4, 5 두개가 되는데 두가지를 따져야하는 것 아닌가? 하는 의문이 들 수 있지만, 완전히 끝나고 바로시작하지 않는 이상 가장 빨리 끝나는 시간 다음에 수업하는 것이 가장 일정을 단축시킬 수 있다.

그리고 만약 만족한다면 4를 pop하고 5~8 수업을 하게 되므로 8을 push한다.

 

요약하면 2개의 우선순위큐가 필요하고, 한개는 모든 수업을 담고 시작시간 순서로 나오는 큐, 강의실의 개수를 저장할 우선순위큐를 사용한다. 그리고 수업을 이어서 할 수 있으면 끝나는 시간을 갱신, 아니면 강의실을 추가(push)한다. 결과적으로 강의실개수 큐의 사이즈가 정답이 된다.

 

문제를 풀면서 이게 왜 공주님 정원 문제와 비슷한지 잘 모르겠다. 문제 시나리오는 비슷해도 풀이가 그래봤자 정렬 이 필요하다는 것 정도..? 밖에 비슷하지 않다.

 

#include<iostream>
#include<queue>

using namespace std;

priority_queue<pair<int, int>> pq;
priority_queue<int> q;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int s, e;
		cin >> s >> e;
		pq.push({ -s,-e });
	}

	q.push(-pq.top().second);

	while (!pq.empty()) {
		int now_start = -pq.top().first;
		int now_end = -pq.top().second;
		pq.pop();

		if (-q.top() <= now_start) {
			q.pop();
			q.push(-now_end);
		}
		else {
			q.push(-now_end);
		}
	}
	
	cout << q.size() << '\n';
}