LeetCode - 253. Meeting Rooms II

비슷한 문제로 프로그래머스에 있는.. 그 기능개발 문제가 생각났다.

근데 그때는 시간 단위가 작았던 것 같아서 시간을 1씩 증가시키면서 반복문을 돌아서 조건 체크를 했다.

이번 문제는 좀 다른 방식으로 접근했다.

처음에 들었던 생각은..

1. 일단은 시작 시간 순서로 오름차순으로 정렬해야겠다!

2. 그런 다음에 방 개수를 저장하듯이 배열에 각 회의의 끝나는 시간을 저장해야겠다.

3. 단 끝나는 시간도 오름차순으로 정렬해야겠다!

4. 다음 회의가 들어오면 그 회의의 시작 시간과, 이미 진행중인 회의들의 끝나는 시간 중 가장 작은 시간을 비교해서 pop/push하기

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> min_end;
        min_end.push(intervals[0][1]);
        int max_size = 1;
        for (int i = 1; i < intervals.size(); i++) {
            vector<int> cur = intervals[i];
            if (min_end.top() <= cur[0]) {
                while(!min_end.empty() && min_end.top() <= cur[0]) {
                    min_end.pop();
                }
                min_end.push(cur[1]);
            } else {
                min_end.push(cur[1]);
                if (max_size < min_end.size())
                    max_size = min_end.size();
            }
        }
        return max_size;
    }
};

priority_queue를 사용해서 끝나는 시간을 오름차순으로 정렬했다.

 

한 가지 디버깅하면서 찾은 부분은, 

문제에 나와있는 2가지 테스트 케이스 외에, 만약 (현재 진행중인 회의들의 끝나는 시간) < (들어오는 회의의 시작 시간)을 만족하는 진행중인 회의들이 여러 개 있을 수 있다.

예를 들어.. [1, 3], [2, 3], [3, 4]. 이럴 경우 priority_queue에서 pop을 2번 한 후 4를 삽입해야 한다.

이 반례를 만족하기 위해 첫 if문 안에 while문을 넣어 pop을 하도록 해야 한다.

이 부분은 처음부터 생각을 했는데, 밑에 케이스를 생각 못 했다.

 

만약 pop을 여러 번 하면, 다음 턴에서 새로운 회의가 들어와도 max_size는 바뀌지 않을 것이다.

예를 들어, 위의 케이스에서 [1, 3], [2, 3], [3, 4], [3, 5] 이렇게 들어왔다고 치자.

[3,4]가 들어오는 순가 기존에 priority_queue에 있던 [1, 3], [2, 3]을 pop해야 한다.

그러고 [3, 4]가 들어와서 현재 priority_queue의 크기가 1로 줄어든다. 하지만 이미 max_size는 이전에 [1, 3], [2, 3]에서 2로 설정되어 있었어서 새로운 회의를 추가해도 max_size는 변경 안 해도 된다.

그래서 두 번째 if문에서 priority_queue의 크기보다 max_size가 더 작을 경우에만 max_size를 변경하도록 했다.