문제 풀이

최소의 강의실을 사용하려면 최대한 겹치지 않게 강의들을 배치해야된다.
먼저 강의 시간들을 오름차순으로 정렬을해서 끝 지점을 기준으로 문제를 해결한다.
정렬된 강의들을 하나씩 순회하면서 현재 강의의 시작 시간이 우선 순위 큐에 들어있는 강의의 끝 시간 보다 크다면 이미 강의가 끝난 것 이므로 그 강의실을 사용해도 되고, 우선 순위큐에 들어있는 강의의 끝 시간보다 작다면 새로운 강의실이 필요하다는 뜻이다.

문제 링크

boj/11000

소스코드

PS/11000.cpp

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>

using namespace std;

int main() {

	int n;
	cin >> n;
	priority_queue<int,vector<int>,greater<int>> pq;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });

	}
	sort(v.begin(), v.end());

	pq.push(v[0].second);
	
	int ans = 1;
	for (int i = 1; i < v.size(); i++)
	{
		while (!pq.empty() && pq.top() <= v[i].first)
			pq.pop();	
		pq.push(v[i].second);
		ans = max(ans, (int)pq.size());
	}
	cout << ans;
}