문제 풀이

회의의 시작시간을 기준으로 정렬을 하고 우선 순위 큐를 사용하여 그리디하게 문제를 풀어나간다.
먼저 정렬을 한 후 첫번째 회의(가장 빠르게 시작하는 회의)의 회의 종료시간을 우선 순위 큐에 push하고
그 다음 회의를 순서대로 순회하면서 q.top() <= v[i].first (현재 회의의 시작 시간보다 이전에 끝난 회의들)인 것들은 회의가 종료 되었으므로 모두 pop해준다.
그렇게 해서 q.size()가 최대 몇개까지 올라갔는지 확인하면 최소 몇개의 회의실을 배정해야 하는지 알 수 있다.

문제 링크

boj/19598

소스코드

PS/19598.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
using namespace std;

vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> q;
int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int s, e;
		cin >> s >> e;
		v.push_back({ s, e });
	}
	sort(v.begin(), v.end());
	q.push(v[0].second);
	int m = 1;
	for (int i = 1; i < n; i++)
	{
		while (!q.empty() && q.top() <= v[i].first)
			q.pop();
		q.push(v[i].second);
		m = max(m, (int)q.size());

	}
	cout << m;
}