백준 19598 - 최소 회의실 개수

문제 설명

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 모든 회의를 진행하려면 필요한 회의실의 최소 개수를 구하면 된다.

 

해당 문제는 정렬을 통해 간단하게 풀 수 있다.

만약 회의가 시작되는 순으로 정렬이 되어 있다고 가정해 보자.

i번째 회의를 진행하려 했을 때 앞서 시작한 회의중 i번째 회의 시작 시간보다 빠르게 종료되는 회의가 있다면 해당 회의실을 그대로 사용할 수 있다.

그러한 회의실이 여러개라면 그중 하나를 선택하게 된다.

즉 i번째 회의보다 일찍 종료되는 모든 회의를 탐색하면 된다.

하지만 하나하나 탐색한다면 $O(N^2)$가 된다.

이를 효율적으로 처리하는 것이 핵심이다.

 

이전에 시작한 회의 중 i번째 시작시간 보다 빠른 것이 몇 개인지 확인하는 효율적인 방법은 우선순위 큐를 사용하는 것이다.

pq에 일찍 끝나는 순으로 기준을 정하고 회의의 끝시간을 추가해 나간다고 하면 i번째 회의가 시작할 때 pq에 있는 것들 중 i번째 시작 시간보다 빨리 종료되는 건 모두 제거하면 된다.

while (!pq.empty() && pq.top() <= meetings[i].first)
{
    pq.pop();
}

그리고 i번째 회의도 종료시간을 pq에 삽입하면 현재 사용하고 있는 강의실은 pq에 유지되게 된다.

따라서 pq의 size를 계속하여 체크하면서 최댓값을 고르면 정답이 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
vector<pair<int, int>> meetings;

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int s, e;
		cin >> s >> e;
		meetings.push_back({ s,e });
	}

	sort(meetings.begin(), meetings.end());

	priority_queue<int, vector<int>, greater<int>> pq;
	int ans = 0;
	pq.push(meetings[0].second);

	for (int i = 1; i < N; i++)
	{
		while (!pq.empty() && pq.top() <= meetings[i].first)
		{
			pq.pop();
		}

		pq.push(meetings[i].second);
		ans = max(ans, (int)pq.size());
	}

	cout << ans;

	return 0;
}

 

---