Meeting Rooms

미팅 룸의 예약 시간을 나타내는 배열 intervals가 들어온다. intervals[i] = [start_i, end_i]는 미팅의 시작 시간과 끝 시간을 나타낸다. 한 사람이 모든 미팅에 참석할 수 있는지 여부를 구하자.

입력 배열의 길이는 1 ~ 10,000 이고 각 미팅 시간의 범위는 0 ~ 1,000,000이다.

겹치는 부분 구하기

미팅을 시작 시간 (또는 끝 시간으로 해도 됨) 기준으로 정렬했을 때, 미팅 범위끼리 겹치는 부분이 있는지를 확인하는 문제이다. 따라서 이전 범위의 끝 시간을 기록해두고, 지금 범위의 시작 시간과 겹치면 곧바로 False이다. 전체를 다 훑었다면 겹치는 부분이 없는 것이므로 참이다.

def canAttendMeetings(invertals):
    prev_end = 0
    for start, end in sorted(intervals, key=lambda x: x[0]):
        if prev_end > start:
            return False
        prev_end = end
    return True

Meeting Rooms II

역시 미팅 룸의 예약 시간 배열 intervals가 주어진다. 이번에는, 모든 미팅을 진행하기 위해서 필요한 최소한의 회의실 개수를 구하자.

예를 들어, intervals = [[0,30], [5,10], [15,20]]이라고 하자. 그러면 [0, 30] 회의와 [5, 10] 회의가 겹치기 때문에 서로 다른 방에서 진행되어야 하므로 일단 회의실이 최소 2개는 필요하다. [15, 20]은 다른 두 회의가 끝나고 나서 진행할 수 있으므로 남는 회의실을 쓰면 된다. 따라서 답은 2이다.

범위는 이전과 같다.

힙

갑자기 난이도가 상승했다. 일단 케이스 하나를 잡고 차근차근 따라가보자.

미팅 시간이 [(1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30)]으로 주어졌다고 하자. 이전과 유사하게 겹치는 부분을 알려면 어느 기준이든 정렬을 해야하므로, 일단 시작 시간 순으로 정렬했다. 그러면 다음 그림처럼 스케쥴링했을 때 회의실을 최소로 사용할 수 있다. 괄호는 시작 시간 기준으로 스케쥴링하는 순서이다.

 시간    : 1  2  3           7  8      10  11    12               19   20                      30
====================================================================================================>
 회의실1 : |-------------(1)------------|   |------------------------(6)------------------------|
 회의실2 :    |-----(2)------|  |-------(4)-------|
 회의실3 :       |----------------------(3)-----------------------|
 회의실4 :                              |---------------(5)------------|

일종의 시뮬레이션을 한다면, 다음과 같은 관찰을 할 수 있다.

• 회의실 목록을 유지한다고 하면, 현재까지 할당된 회의실 중 가장 빨리 끝나는 회의실 정보가 필요하다.
• 괄호 안의 순서를 보면 회의실 1, 2, 3에 차례로 회의실 1, 2, 3이 할당된 이유는, 기존 회의실 중에서 가장 빨리 끝나는 회의가 지금 할당하려는 회의와 겹치기 때문이다. 즉, 두번째 회의 (2, 7)을 할당하려고 할 때, 이미 진행 중인 회의 (1, 10)이 아직 끝나지 않았으므로 (10 > 2) 어쩔 수 없이 새 회의실에 할당해야 한다.
• 반면 네번째 회의인 (8, 12)가 들어왔을 때, 지금 진행 중인 회의실 중에서 가장 빨리 끝나는 회의인 (2, 7)가 끝난 이후라서 (8 > 7) 이 회의실을 재활용할 수 있다.
• 회의실을 재활용 한다는 것은 곧 가장 빨리 끝나는 기존 회의를 지금 회의로 바꾼다는 것이다. 즉, 가장 빨리 끝나는 회의를 빼고 지금 회의 정보를 넣는다. 이때 이후 스케쥴링을 위해 회의실 목록은 항상 가장 빨리 끝나는 회의를 빨리 알 수 있으면 좋겠다. 여기에 적절한 자료구조는 최소힙이다.
• 마지막 미팅까지 끝냈을 때, 이때까지 예약된 회의실의 개수가 최소 회의실의 개수이다.

이 아이디어를 구현하면 다음과 같다.

import heapq
def minMeetingRooms(intervals):
    sorted_itvs = sorted(intervals, key=lambda x: x[0])
    occupied = [sorted_itvs[0][1]]

    for start, end in sorted_itvs[1:]:
        if occupied[0] <= start:
            heapq.heapreplace(occupied, end)
        else:
            heapq.heappush(occupied, end)
    return len(occupied)

• 회의실 목록을 최소힙으로 유지한다. 이때 우리가 관심있는 것은 회의가 끝나는 시간이므로, 시작 시간은 무시하고 그냥 끝나는 시간만 담으면 된다.
• 파이썬에서의 최소힙은 단지 heapq 함수를 이용해서 원소의 추가와 삭제를 해서 성질을 유지하는 것만 빼면 첫번째 원소가 최소값인 리스트와 같다. 따라서 occupied[0]으로 곧바로 현재 회의실 중 가장 빨리 끝나는 회의 시간을 알 수 있다.
• 회의실을 재활용한다는 것은 가장 빨리 끝나는 회의실에서 지금 회의를 할당하는 것이다. 재활용이 안되는 경우는 항상 새 회의실을 할당해야 하므로 곧바로 푸시한다.