[ leetcode 문제풀이 ] Meeting Rooms II

Meeting Rooms II - LeetCode

Account Login - LeetCode

(Meeting Rooms II 문제는 LeetCode Premium 문제로 위 링크 혹은 LintCode를 통해 풀어보실 수 있습니다.)

 

 

 

< Meeting Rooms II 문제 설명 > 

 

Meeting Rooms II 문제는 다음과 같다. 

Given an array of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ... ] (si < ei), find the minimum number of conference rooms required.

 

회의의 시작시간과 종료시간으로 이루어진 구간의 집합이 주어졌을 때 필요한 회의실의 최소 개수를 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

 

< Meeting Rooms II 문제 접근 > 

 

이 문제의 related topic으로 나와있는 sweep line algorithm을 사용하면 쉽게 풀 수 있다. 사실 이 문제를 접하기 전까지는 몰랐는데 sweep line algorithm은 interval의 다른 문제 (merge intervals, non-overlapping intervals, meeting rooms)에서 은연중에 사용한 방법들이었다.

 

나는 sweep line algorithm의 기본 틀과 Shamos-Hoey Algorithm에서 event point라는 집합을 정의하는 방식을 적용해 알고리즘을 작성하였다. 작성한 코드를 먼저 보면 다음과 같다. (Cpp 사용)

 

#include <algorithm>

struct EndPoint{
    int pointVal;
    bool isStart = false;
};

static bool cmp(EndPoint p1, EndPoint p2){
    if(p1.pointVal == p2.pointVal){
        if(p1.isStart) return false;
        if(p2.isStart) return true;
    }
    return p1.pointVal < p2.pointVal;
}

int minMeetingRooms(vector<vector<int>> &intervals) {
    int n = intervals.size();
    if(n == 1) return 1;

    EndPoint* PointSet = new struct EndPoint[2*n];

    for(int i=0;i<n;i++){
        PointSet[2*i].pointVal = intervals[i][0];
        PointSet[2*i].isStart = true;
        PointSet[2*i+1].pointVal = intervals[i][1];
        // PointSet[2*i+1].isStart = false; : default
    }
    sort(PointSet, PointSet+2*n, cmp);

    int maxRooms = 0, roomCount = 0;
    for(int i=0;i<2*n;i++){
        if(PointSet[i].isStart)
            maxRooms = max(maxRooms, ++roomCount);
        else --roomCount;
    }
    return maxRooms;
} // runtime : 41 ms, memory usage : 4.68 MB (by LintCode)

 

각 부분의 구성에 대해 살펴보면 다음과 같다. 

 

EndPoint 구조체 : meeting schedule의 start와 end 시간을 저장함

→ pointVal은 시간의 값을 , isStart는 point가 시작점이면 true를 종료점이면 false를 저장

 

cmp 비교함수 : EndPoint 구조체로 이루어진 집합을 정렬하기 위한 비교함수로 pointVal 값을 기준으로 오름차순 정렬하되, 두 EndPoint의 pointVal이 동일할 경우 EndPoint가 종료점인 경우가 우선순위를 갖도록 함→ 이렇게 함으로써 meeting의 종료를 먼저 카운트하고 meeting의 시작을 카운트하여 meeting이 연달아 있는 경우 추가적인 meeting room이 필요없다는 것을 고려함.

 

maxRooms : 필요한 meeting room의 값

→ 동시간대에 중첩되는 회의의 최대 값을 세어주면 됨 roomCount : 동시간대에 중첩되는 회의의 값을 count/update

 

만약 PointSet[i](=EndPoint)가 meeting의 시작점인 경우 동시간대 회의 수 +1

       PointSet[i](=EndPoint)가 meeting의 종료점인 경우 동시간대 회의 수 -1