BOJ 11000 강의실 배정

BOJ 11000 강의실 배정

문제링크 : https://www.acmicpc.net/problem/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";
}