Leetcode - 253. Meeting Rooms II

문제

미팅룸 예약 시간이 담긴 배열이 주어질때, 모든 미팅을 수용할 수 있도록 필요한 최소 미팅룸 갯수를 구하라.[시작시간, 종료시간]

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

https://leetcode.com/problems/meeting-rooms-ii/

해결 O(NlogN)

먼저 시작시간 기준으로 예약을 정렬한다. 그 뒤 다이어그램을 그려보면 순서대로 시작시간을 만나면 방갯수 +1, 종료시간을 만나면 -1을 하고 최대값을 저장해놓으면 그게 해답이 된다.

가령 예약시간이 [[0,30],[5,10],[15,20]] 으로 정렬되어있을때, 시작, 종료를 순차적으로 정렬해서 나열하면 아래와 같다. (괄호)가 시작시간, 아니면 종료시간.

(0) (5) 10 (15) 20 30
 1   2   1   2   1  0

그리고 미팅룸 갯수를 순차적으로 계산하면 최대값이 2가 된다.

여러가지 솔루션으로 해결이 가능해서 코딩테스트 문제로 딱 좋을만한 문제인듯!

#define max(a,b) (((a) > (b)) ? (a) : (b))

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize)
{
    int *start = (int *)calloc(intervalsSize, sizeof(int));
    int *finish = (int *)calloc(intervalsSize, sizeof(int));
    for (int i = 0; i < intervalsSize; i++) {
        start[i] = intervals[i][0];
        finish[i] = intervals[i][1];
    }
    qsort(start, intervalsSize, sizeof(int), cmp);   
    qsort(finish, intervalsSize, sizeof(int), cmp);   
    
    int ret = 0;
    int max_room = 0;
    int st_i = 0;
    int fi_i = 0;
    while (st_i < intervalsSize && fi_i < intervalsSize) {
        if (start[st_i] == finish[fi_i]) {
            st_i++;
            fi_i++;
        } else if (st_i < intervalsSize && (start[st_i] < finish[fi_i] || fi_i == intervalsSize)) {
            ret++;
            st_i++;
            max_room = max(ret, max_room);
        } else if (fi_i < intervalsSize && (finish[fi_i] < start[st_i] || st_i == intervalsSize)) {
            ret--;
            fi_i++;
            max_room = max(ret, max_room);
        }
    }
    return max_room;
}