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

오랜만에 깔끔하고 빠르게 풀어서 기분이 좋아서 포스팅한다. 깔깔
정렬 관련 문제를 많이 풀어봐서 빠르게 해답이 떠올랐던 거 같다.

문제링크

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

설명

최소의 강의실을 사용해서 모든 수업을 가능하게 해야 하는 문제이다.

저퀄리티 그림 죄송합니다...

우선 강의가 끝나는 시간이 큰 순으로 endheap에 담는다.

강의가 시작되는 시간이 큰 순으로 startheap에 담아가면서 만약 endheap.top()의 강의가 끝나는 시간이 startheap.top()의 강의가 시작하는 시간보다 작거나 같다면 둘을 합쳐서 다시 startheap에 넣어준다.

만약 더 크다면 같은 강의실에서 들을 수 없는 강의이므로, startheap에 그냥 넣어준다.

endheap이 빌 때까지 이 과정을 반복하면 startheap의 크기가 필요한 강의실의 최소 개수가 된다.

코드

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, start, end;
	priority_queue<pair<int, int>> endheap, startheap;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> start >> end;
		endheap.push({ end, start });
	}
	while (!endheap.empty())
	{
		start = endheap.top().second;
		end = endheap.top().first;
		endheap.pop();

		if (startheap.empty() || startheap.top().first < end)
			startheap.push({ start, end });

		else
		{
			end = startheap.top().second;
			startheap.pop();
			startheap.push({ start, end });
		}
	}
	cout << startheap.size();
	return 0;
}