BOJ 11000 강의실 배정

문제 링크 : https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

요약

N개의 수업 시작시간과 끝 시간이 주어질 때 이 수업을 다 가능하게 하는 최소 강의실 개수를 구해라 (수업이 끝난 직후에 수업을 시작을 할 수 있다.)

풀이

BOJ 1931 회의실배정 과 유사한 문제이지만 회의실 배정은 한 개의 회의실에 얼마나 많은 회의를 중복 없이 넣을 수 있는지를 구하는 문제였고 이 문제는 모든 시간의 강의를 전부 가능하게 할 수 있는 강의실 최소 개수를 구하는 문제이다.

일단 시작점을 기준으로 정렬을 해서 벡터에 넣어준고 젤 처음 회의 시간의 끝점을 최소힙에 넣어준다(모든 강의를 가능하게 해야 하므로 존재하는 강의 중 가장 빠르게 끝나는 시간을 찾아 비교해줘야 함). 순서대로 탐색하면서 시작시간이 최소 힙의 top값(젤 빠르게 강의가 끝나는 시간)과 비교했을 때 작으면 시간이 겹치는 경우이므로 최소 힙에 또 끝 값을 넣어준다, 만약 같거나 크다면 시간이 겹치지 않으므로 최소 힙의 top값을 pop 해주고 새로운 끝 값을 push 해준다. 이것을 전부 진행하면서 가장 최소 힙의 사이즈가 컸던 순간이 수업을 전부 가능하게 하는 최소 강의실 개수가 된다.

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
priority_queue<int>pq;
vector<pair<int, int>>q;
int n,s,e,ans=-1e9;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> e;
		q.push_back({ s,e });
	}
	sort(q.begin(), q.end());
	pq.push(-q[0].second);
	for (int i = 1; i < n; i++) {
		if (q[i].first >=-pq.top()) {
			pq.pop();
			pq.push(-q[i].second);
		}
		else if (q[i].first < -pq.top()) {
			pq.push(-q[i].second);
		}
		int size = pq.size();
		if (ans <= size) {
			ans = size;
		}

	}
	
	cout << ans << "\n";
}