문제 개요
회의 시간 구간 배열이 주어졌을 때, 필요한 최소 회의실 개수를 구하는 문제입니다. 각 구간은 시작 시간과 종료 시간의 쌍 [[s1,e1],[s2,e2],...] 형태로 표현되며, 모든 쌍은 si < ei 조건을 만족합니다.
예를 들어 입력이 [[0, 30], [5, 10], [15, 20]]이라면 출력은 2가 됩니다. 첫 번째 회의(0~30)가 진행되는 동안 두 번째 회의(5~10)가 겹치므로 회의실이 하나 더 필요하고, 세 번째 회의(15~20)는 두 번째 회의가 끝난 뒤 같은 회의실에서 진행할 수 있기 때문입니다.
접근 방법
이 문제는 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 우선순위 큐 pq를 하나 정의합니다.
- 구간 배열 intervals를 정렬합니다.
- 결과값 ret := 0으로 초기화합니다.
- i := 0부터 intervals의 크기까지 반복하면서 다음을 수행합니다.
- pq가 비어 있지 않고 pq의 top 원소가 intervals[i][0] 이하인 동안 pq에서 원소를 제거합니다.
- intervals[i]를 pq에 삽입합니다.
- ret := max(ret, pq의 크기)로 갱신합니다.
- 최종적으로 ret을 반환합니다.
우선순위 큐에는 아직 종료되지 않은 회의들이 저장됩니다. 새로운 회의가 시작될 때 이미 종료된 회의들을 큐에서 제거하면, 큐에 남아 있는 원소의 개수가 곧 동시에 진행 중인 회의의 수, 즉 필요한 회의실의 개수가 됩니다. 종료 시간이 가장 빠른 회의를 빠르게 확인하기 위해 최소 힙 구조의 우선순위 큐를 사용합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(vector<int>& a, vector<int>& b){
return !(a[1] < b[1]);
}
};
class Solution {
public:
static bool cmp(vector<int> a, vector<int> b){
return (a[1] < b[1]);
}
int minMeetingRooms(vector<vector<int>>& intervals) {
priority_queue<vector<int>, vector<vector<int> >, Comparator> pq;
sort(intervals.begin(), intervals.end());
int ret = 0;
for (int i = 0; i < intervals.size(); i++) {
while (!pq.empty() && pq.top()[1] <= intervals[i][0])
pq.pop();
pq.push(intervals[i]);
ret = max(ret, (int)pq.size());
}
return ret;
}
};
int main(){
vector<vector<int>> v = {{0, 30}, {5, 10}, {15, 20}};
Solution ob;
cout << (ob.minMeetingRooms(v));
}
실행 결과
입력:
{{0, 30}, {5, 10}, {15, 20}}출력:
2
복잡도 분석
구간 배열을 정렬하는 데 O(n log n)의 시간이 소요되며, 각 구간마다 우선순위 큐에 삽입과 삭제 연산이 최대 한 번씩 발생하므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 최악의 경우 모든 회의가 서로 겹쳐 큐에 n개의 원소가 저장되는 상황을 고려하면 O(n)입니다.