[그리디 #16] BOJ 19598 - 최소 회의실 개수

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

19598번: 최소 회의실 개수

 

계속된 실패..

비슷한 문제인 회의실 배정 문제에선 끝나는 시간을 기준으로 정렬하여 진행하였다.

이와는 다른 방법을 생각해보다 회의 시간이 짧은 것을 기준으로 해보면 어떨까라고 생각했다.

 

이를 이용해 어떻게든 해보려고 했는데 실패하고, 안되는 이유를 찾아보았다.

 

출처: https://source-sc.tistory.com/59

출처: https://source-sc.tistory.com/59

아무리 끝나는 회의 시간이 짧더라도 끝나는 시간이 짧을 수록 이득을 볼 수 있기 때문에 이는 틀린 아이디어이다.

 

접근 방법

회의가 끝나는 시간이 빠를수록 뒤에 올 수 있는 회의가 많아진다.

기본적인 이 아이디어를 이용해보자.

 

원래 하던 방식은 기존 회의 문제서 사용했기 때문에, 우선순위 큐를 사용한 블로그들을 참고했다..

 

vector<pair<int,int>> v : ( { 시작시간, 종료시간 } , ... )

priority_queue<int,vecotr<int>, greater<int>> pq : (종료 시간, 종료 시간, ...) : 사용 중인 회의실(종료 시간을 오름차순으로 설정)

 

1. v에 시작시간과 종료시간을 넣은 후, 오름차순 sort

2. v를 for문 돌면서 pq의 top과 v의 first를 비교한다.

2-1. pq.top > v[i].first  => 회의 v[i]의 시작 시간에는 회의실 pq.top에선 회의가 진행중이다. => 새로운 회의실을 이용해야 한다.

2-2. pq.top <= v[i].first => 회의 v[i]의 시작 시간에는 회의실 pq.top의 회의가 끝나서 이용 가능하다. => 종료된 회의 pq.top을 pop 한다.

3. pq.size() = 회의실 개수 이므로 회의실 개수의 max를 저장해둔다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

vector<pair<int, int>> times;
priority_queue<int, vector<int>, greater<int>> pq;
int n;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		times.push_back({ a, b });
	}

	sort(times.begin(), times.end());
	
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		
		while (!pq.empty() && pq.top() <= times[i].first) {
			// 같은 회의실에서 사용가능하므로 pop
			pq.pop();
		}
		pq.push(times[i].second);
		cnt = max(cnt, (int)pq.size());
	}

	cout << cnt;
}