[백준/BOJ] 11000번 강의실 배정 (C++)

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

11000번: 강의실 배정

강의실을 적게 사용하기 위해서 시작 시간과 끝 시간의 간격을 최대한 좁혀야 한다. 그러므로 시작 시간을 기준으로 오름차순 정렬하였다. 그리고 우선순위 큐를 이용하여 수업 끝 시간을 넣어준다. 현재 수업의 시작 시간이 우선순위 큐에 들어있는 top의 값보다 크거나 같으면 강의실을 같이 쓸 수 있으므로, pop한 후 우선순위 큐에 현재 수업의 끝 시간을 넣어준다. 반대의 경우에는 pop없이 push만 해준다. 그러면 우선순위 큐에 남은 원소의 수가 필요한 최소 강의실 수가 된다.

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<pair<int, int> > v(n);
	priority_queue<int, vector<int>, greater<int> > pq;
	for(int i = 0; i < n; i++) {
		int s, e;
		cin >> s >> e;
		v[i] = make_pair(s, e);
	}
	sort(v.begin(), v.end());
	pq.push(v[0].second);
	for(int i = 1; i < n; i++) {
		if(pq.top() <= v[i].first) {
			pq.pop();
		} 
		pq.push(v[i].second);
	}
	
	cout << pq.size();
}