백준 19598번 최소 회의실 개수 (C++)

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

19598번: 최소 회의실 개수

 

 처음 봤을 때 우선순위큐가 생각이 났지만 구체적으로는 생각해내지 못했던 문제. 

중요한 것은 회의실을 사용하고 있는 것을 어떻게 나타낼 것인가이다. 

 

여기서는 우선순위큐를 회의실로 생각한다.

 

1. 먼저 가장 빨리 시작하면서 가장 일찍 끝나는 일정을 시작한다. 1~2시 회의, 1시~4시 회의가 있다면 1~2시 회의를 시작하고 끝나는 시간을 우선순위큐에 넣는다.

2. 이후 다음 회의 시작 시간이 지금 우선순위큐의 top 즉 가장 빨리 끝나는 회의 시간보다 높다? 그러니까, 4시에 끝나는데 3시에 시작한다면 회의실을 추가배정한다.

3. 만약 가장빨리 끝나는 회의시간과 같거나 늦은시간이라면 그 회의를 끝낸다.(pop)

4. 큐의 크기가 답이된다.

 

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

bool comp(pair<int, int>& a, pair<int, int>& b) {
	if (a.first < b.first) return true;
	else if (a.first == b.first) return a.second < b.second;
	else return false;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;

	cin >> n;

	priority_queue<int, vector<int>, greater<>> pq;
	vector<pair<int, int>> meets;


	for (int i = 0; i < n; i++) {
		int st;
		int ed;
		cin >> st >> ed;
		meets.push_back(make_pair(st, ed));
	}

	sort(meets.begin(), meets.end(), comp);

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

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

	cout << pq.size() << '\n';

	return 0;
}