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

문제 링크: https://www.acmicpc.net/problem/19598

19598번: 최소 회의실 개수

1. 주의할 점

- 정렬기준을 잡는다

- 2개의 우선순위큐를 이용한다

 

2. 구현

- 각 입력에 대한 정보들을 시작시간에 대한 오름차순, 종료시간에 대한 내림차순으로 정렬하는 우선순위큐 PQ에 담는다

- 현재 진행중인 회의에 대한 종료시간을 담는 우선순위 큐 haveRight에 PQ의 첫 원소의 종료시간을 담고 시작한다

- haveRight 우선순위큐는 오름차순으로 정렬한다

- 우선순위 큐 PQ에 원소가 없을 때까지 1개씩 빼내면서 haveRight의 Top원소와 비교하여 회의시간이 겹치는 경우 haveRight에 추가한다

- 겹치지 않는 경우, haveRight에 원소가 없을때까지 비교하여 회의시간이 겹치는 경우 종료하고 현재 PQ에서 꺼낸 회의 종료시간을 haveRight에 담는다

- haveRight의 원소의 개수가 곧 회의실 개수이므로 Answer와 비교하여 최대값을 계속 갱신한다

- 위 과정을 계속 반복한다 

 

※ 풀면서 생각한 몇 가지 TC(정렬 안된 상태)

TC #1
6
1 10
3 8
4 6
4 6
7 11
7 11
----------
  ------
   ---
   ---
      -----
      -----

TC #2
4
1 10
3 7
4 9
7 11
----------
  ----
   ------
      -----

TC #3
4
1 10
3 8
3 9
8 11
----------
  ------
  -------
        ----

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int left, right;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.left == b.left)		return a.right < b.right;
		return a.left > b.left;
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, a, b, result = 1;
	cin >> num;
	priority_queue<info, vector<info>, cmp> pq;
    priority_queue<int,vector<int>,greater<int>> haveRight;
    
	for (int i = 0; i < num; i++) {
		cin >> a >> b;
		pq.push({ a,b });
	}
	info ii;
	ii = pq.top();
	pq.pop();
	haveRight.push(ii.right);
	int len;

	while (!pq.empty()) {
		int cl = pq.top().left;
		int cr = pq.top().right;
		int hr = haveRight.top();
		pq.pop();
		if (cl < hr)	haveRight.push(cr);
		else {
			haveRight.pop();
			while (!haveRight.empty()) {
				hr = haveRight.top();
				if (cl < hr) break;
				haveRight.pop();
			}
			haveRight.push(cr);
		}
		len = haveRight.size();
		result = max(result, len);
	}
	cout << result;
	return 0;
}