[C++] 백준 11000번 강의실 배정

여러가지 수업이 각 시간마다 주어졌을 때 최소 몇개의 강의실이 필요한지 찾는 문제입니다.

시작시간을 기준으로 정렬을 해주고 차례대로 확인을 합니다.

시작부분을 우선순위 큐(pq)에 넣어줍니다.
pq의 값 가장 빨리 끝나는 강의실에 넣을 수 있으면 현재 시작위치를 넣을 수 있으면 그 pq를 갱신해줍니다.
만약 넣지 못한다면 pq를 하나 더 만들어주는 식으로 진행합니다.

 

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

int main(int argc, char* argv[])
{
	int n;
	pair<int, int> p[200001];
	priority_queue<int, vector<int>, greater<int> > pq;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> p[i].first >> p[i].second;
	}

	sort(p, p + n);

	pq.push(p[0].second);

	for (int i = 1; i < n; ++i) {
		if (pq.top() <= p[i].first) {
			pq.pop();
			pq.push(p[i].second);
		}
		else {
			pq.push(p[i].second);
		}
	}

	cout << pq.size() << endl;

	return 0;
}