1374번: 강의실

문제링크: 1374번: 강의실

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

설명

강의실을 하나의 우선순위 큐에 넣어두고 가장 빠르게 수업이 마치는 교실을 추적하면서 강의를 배정하는 되는 문제이다. 여기서 중요한 점은 강의 스케줄을 '끝나는 시간'을 우선적으로 정렬해야 한다는 점이다. 처음에는 시작 시간을 기준으로 정렬했는데 오답이 나왔다.

정렬된 강의 스케줄로 하나씩 교실에 배정하는데 큐에 있는 교실에 바로 강의를 진행할 수 있으면 바로 배정하고 진행할 수 없으면 큐에 새로운 교실을 추가해주는 방식으로 진행하면 문제를 해결할 수 있다.

코드

#include <iostream>
#include <queue>
#include <algorithm>
#define endl '\n'

using namespace std;

bool compare(pair<int, int> p1, pair<int, int> p2) {
	if (p1.first == p2.first)
		return p1.second < p2.second;
	return p1.first < p2.first;
}

void solve() {
	int N;
	vector<pair<int, int>> v;
	cin >> N;
	v.resize(N);
	for (int i = 0; i < N; ++i) {
		int a;
		cin >> a >> v[i].first >> v[i].second;
	}
	sort(v.begin(), v.end(), compare);

	priority_queue<int, vector<int>, greater<int>> pq;
	for (auto p : v) {
		int start = p.first, end = p.second;
		if (!pq.empty() && start >= pq.top()) {
			pq.pop();
		}
		pq.push(end);
	}
	cout << pq.size();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}