[C++]백준 11000번: 강의실 배정

문제 출처

풀이

우선 문제를 보면 기존의 그리디 알고리즘으로 풀리던 강의실 문제 유형과는 다르다. 이 문제는 한 강의실에 최대 몇 개의 강의가 들어갈 수 있냐고 묻는 그리디 알고리즘 형태의 문제가 아니라. 모든 강의를 수용 할 수 있는 강의실의 개수를 원한다.

이 문제는 우선순위 큐를 사용하여 풀 수 있다. 우선 모든 강의를

1. 시작 시간 순서대로 정렬한다.
2. 시작 시간이 같다면 끝나는 시간이 빠른 순서대로 정렬한다.

이 두가지 규칙을 이용하여 정렬을 한다. 그 다음 우선순위 큐를 생성하여 강의의 끝나는 시간을 오름차순으로 담는다. 우선순위 큐에 다음과 같은 규칙을 적용한다.

1. i번째 강의의 끝나는 시간을 우선순위 큐에 담는다.
2. 우선순의 큐의 top을 확인하여 top보다 i번째 강의의 시간시간이 더 크다면 pop을 통해 기존의 top에 존재하던 강의를 빼버린다.

2번이 이해하기 어려울 수 있는데 그냥 i번째 강의를 넣고 top을 pop하는 순간 같은 강의실을 쓰는 강의라고 생각하면 편하다.
우리는 이미 강의를 1.시작시간으로 정렬 2. 시작시간이 같으면 끝나는 시간으로 정렬을 했다. 따라서 i번째 강의를 우선순위 큐에 넣을 때 i번째 강의는 남은 다른 강의들보다 시작시간이 가장 빠른 강의이다. 우선순위 큐의 top에는 가장 빠른 끝나는 시간이 담겨 있기 때문에 2번 규칙은 자연스럽게 이 두개를 비교하는 것이다.
그렇다면 우선순위 큐의 원소의 개수가 바로 빌려야하는 강의실의 개수가 되는 것이다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> ii;


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<ii> array(N);
	priority_queue<int, vector<int>, greater<int>> que;
	for ( int i = 0; i < N; i++ ) {
		int t1, t2;
		cin >> t1 >> t2;
		array[i].first = t1;
		array[i].second = t2;
	}
	sort(array.begin(), array.end());
	for ( int i = 0; i < N; i++ ) {
		que.push(array[i].second);
		if ( que.top() <= array[i].first )que.pop();
	}

	cout << que.size() << endl;

	return 0;
}