Leetcode - 252. Meeting Rooms

문제

주어진 배열에는 미팅시간(시작,종료) 리스트가 담겨있다. 한 사람이 모든 미팅에 참여할수 있는지 판단하라.

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

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

해결 아이디어

• brute force
  미팅 시간의 최대범위까지(1000001) 배열을 만들고 각 미팅시간을 표시한다. 미팅 시간을 하나씩 순회하며 이전에 표시가된 배열값을 만나면 false 리턴.
• sorting
  미팅 시간을 시작시간 기준으로 정렬한다. 그 위 미팅시간을 순서대로 순회하면서 중첩이 되는 부분을 만나면 false시키면 된다.

해결 1 - brute force

#define MAX_TIME 1000001
int timeline[MAX_TIME];

bool canAttendMeetings(int** intervals, int intervalsSize, int* intervalsColSize){
    memset(timeline, 0, sizeof(int) * MAX_TIME);
    
    for (int i = 0; i < intervalsSize; i++) {
        for (int j = intervals[i][0]; j < intervals[i][1]; j++) {
            if (timeline[j] != 0)
                return false;
            timeline[j]++;
        }
    }
    return true;
}

해결 2 - O(NlogN)

추가로 2차원배열을 qsort로 정렬하는 방법 참고하기.
인자로 전달된 값을 우선 (int **)로 형변환 해야함.

int cmp(const void *a, const void *b)
{
    int *aval = *(int **)a;
    int *bval = *(int **)b;
    return aval[0] - bval[0];
}

bool canAttendMeetings(int** intervals, int intervalsSize, int* intervalsColSize){
    qsort(intervals, intervalsSize, sizeof(int *), cmp);
    for (int i = 0; i < intervalsSize - 1; i++)
        if (intervals[i][1] > intervals[i + 1][0])
            return false;
    return true;
}