Meeting Rooms II | 알고달레

LeetCode의 253번째 문제인 Meeting Rooms II를 함께 풀어보도록 하겠습니다.

이 문제는 LeetCode에서 유료 구독자만 접근할 수 있습니다. LintCode의 919번째 문제가 거의 동일하며 무료로 푸실 수 있으니 참고 바랍니다.

문제

intervals[i] = [starti, endi] 형태의 구간으로 이뤄진 회의 시간을 나타내는 배열이 주어졌을 때, 필요한 최소한의 회의실의 개수를 구하십시오.

예제

입력: [[0,30],[5,10],[15,20]]
출력: 2

입력: [[7,10],[2,4]]
출력: 1

풀이 1: 최소 힙

문제에서 요구하는 최소한으로 필요한 회의실의 개수를 구하려면 하나의 회의실에서 최대한 많은 회의를 해야될텐데요. 어떻게 하면 새로운 회의를 시작하려고 할 때, 이전에 사용했던 회의실 중에서 재사용이 가능한 회의실이 있는지 알아낼 수 있을까요?

바로, 여태까지 시작한 회의 중에서 가장 일찍 끝난 회의만 고려하면 됩니다. 그 회의가 아직 안 끝났다면 다른 회의도 모두 안 끝났을테니까요.

가장 일찍 끝난 회의의 종료 시간이 새로운 회의의 시작 시간보다 더 이르다면 우리는 해당 회의실을 재사용할 수 있습니다. 하지만 가장 일찍 끝난 회의의 종료 시간이 새로운 회의의 시작 시간보다 더 늦는다면 우리는 회의실을 하나 더 필요하게 됩니다.

즉, 가장 일찍 끝난 회의의 종료 시간과 다음 회의의 시작 시간과 비교하여, 남는 회의실이 없어서 회의실이 하나 더 필요한지, 아니면 기존에 다른 회의에서 쓰던 회의실을 재사용할 수 있는지 판단할 수 있습니다.

가장 일찍 끝난 회의의 종료 시간 <= 다음 회의의 시작 시간 👉 회의실 재사용 가능
가장 일찍 끝난 회의의 종료 시간 > 다음 회의의 시작 시간 👉 회의실 하나 더 필요

이런 상황에서는 최소 힙 (Min Heap)이라는 자료구조를 사용하면 딱인데요. 최소 힙에 여태까지 시작한 회의의 종료 시간을 저장해놓으면 가장 일찍 끝난 회의의 종료 시간을 O(1), 즉 상수 시간에 알아낼 수 있기 때문입니다.

기본 아이디어는 주어진 입력 배열을 시작 시간 순으로 우선 정렬을 해놓고, 입력 배열을 루프 돌면서 최소 힙에 종료 시간을 하나씩 추가하는데요. 만약에 가장 일찍 끝난 회의의 종료 시간이 다음 회의의 시작 시간보다 이른 경우에만, 기존 회의실을 재사용할 수 있으므로 힙에서 가장 일찍 끝난 회의의 종료 시간을 제거합니다. 루프가 끝나면 최종적으로 최소 힙에 남아있는 종료 시간의 개수가 바로 최소한으로 필요한 회의실의 개수가 될 것입니다.

이 알고리즘을 문제에서 주어진 첫 번째 예제에 적용해볼께요.

 _____
[0, 30], [5, 10], [15, 20]
최소 힙: []

👉 첫 번째 회의를 위해서 회의실 하나 무조건 필요
push 30
최소 힙: [30]

          _____
[0, 30], [5, 10], [15, 20]
최소 힙: [30]

30 > 5 👉 회의실 하나 더 필요
push 10
최소 힙: [10, 30]

                   ______
[0, 30], [5, 10], [15, 20]
최소 힙: [10, 30]

10 < 15 👉 회의실 재사용 가능
pop 10
push 20
최소 힙: [20, 30]

그럼 이 알고리즘을 파이썬으로 구현해볼까요?

from heapq import heappush, heappop

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        ends = []
        for start, end in intervals:
            if ends and ends[0] <= start:
                heappop(ends)
            heappush(ends, end)
        return len(ends)

입력 배열의 크기를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(nlog(n))이 되는데요. 정렬에 O(nlog(n)) 시간이 소요되고, O(log n), 즉 로그 시간이 소요되는 힙에 데이터 추가나 삭제하는 작업을 n번 반복하기 때문입니다. 반면에 공간 복잡도는 최악의 경우 힙의 크기가 n이 될 수 있어서 O(n)입니다.

풀이 2: 따로 정렬

입력 배열을 시작 시간으로 정렬하면 새로운 회의실이 언제 필요한지는 순서대로 알 수 있지만, 기존에 쓰던 회의실이 언제 필요가 없어지는지는 그 순서를 알 수가 없는데요. 만약에 시작 시간과 종료 시간을 따로 정렬하면 어떨까요? 그러면 회의실이 언제 필요가 없어지는지도 순서대로 알 수 있겠죠?

예를 들어, 첫 번째 예제에서 주어진 입력 배열을 시작 시간과 종료 시간으로 분리하여 정렬해보겠습니다.

입력 배열: [[0, 30], [5, 10], [15, 20]]
시작 시간: [0, 5, 15]
종료 시간: [10, 20, 30]

그리고 시작 포인터가 가리키는 시간과 종료 포인터가 가리키는 시간을 비교하면서 2개의 배열을 동시에 탐색하면, 추가 회의실이 필요한 시점과 기존 회의실이 필요 없어지는 시점을 찾을 수 있을 것입니다.

          s
시작 시간: [0, 5, 15]
종료 시간: [10, 20, 30]
          e

0 < 10 👉 회의실 하나 더 필요함
필요한 회의실: 1
s++

             s
시작 시간: [0, 5, 15]
종료 시간: [10, 20, 30]
          e

5 < 10 👉 회의실 하나 더 필요함
필요한 회의실: 2
s++

                s
시작 시간: [0, 5, 15]
종료 시간: [10, 20, 30]
          e

15 > 10 👉 회의실 하나 필요 없음
필요한 회의실: 1
e++

                s
시작 시간: [0, 5, 15]
종료 시간: [10, 20, 30]
              e

15 < 20 👉 회의실 하나 더 필요함
필요한 회의실: 2
s++

이런 식으로 시작 포인터가 배열의 끝에 도달하면 모든 시작 시간을 고려하게 되었으며 남은 종료 시간은 굳이 고려할 필요가 없습니다. 우리가 구해야하는 것은 회의실이 가장 많이 필요할 때의 회의실 개수이고, 남은 종료 시간은 오직 필요한 회의실의 개수를 감소시키기만 할테니까요.

그럼 이 알고리즘을 파이썬으로 구현해보겠습니다.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(i[0] for i in intervals)
        ends = sorted(i[1] for i in intervals)

        max_cnt, cnt = 0, 0
        s, e = 0, 0
        while s < len(starts):
            if starts[s] < ends[e]:
                cnt += 1
                max_cnt = max(cnt, max_cnt)
                s += 1
            else:
                cnt -= 1
                e += 1
        return max_cnt

입력 배열의 크기를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(nlog(n))이 되는데요. O(nlog(n)) 시간이 걸리는 정렬을 두 번 수행한 후에, 2n만큼의 반복을 하고 있기 때문입니다. 즉, 빅오 계산법에 따라서 O(2nlog(n) + 2n) = O(nlog(n))이 성립하게 됩니다. 반면에 공간 복잡도는 두 개의 추가 배열이 2n의 추가 공간을 사용하므로 O(n)이 되겠습니다.

풀이 3: 같이 정렬

모든 회의가 언제 시작하고 언제 끝나는지를 하나의 시간 선상에서 순서대로 표시해보면 어떨까요? 예를 들어, 첫 번째 예제에서 주어진 회의들이 시간이 지남에 따라서 언제 시작하고 언제 끝나는지를 시각화해보겠습니다.

입력 배열: [[0, 30], [5, 10], [15, 20]]

 0: [0, 30] 시작 👉 회의실 1개 필요 (+1)
 1:
 2:
 3:
 4:
 5: [5, 10] 시작 👉 회의실 2개 필요 (+1)
 6:
 7:
 8:
 9:
10: [5, 10] 종료 👉 회의실 1개 필요 (-1)
11:
12:
13:
14:
15: [15, 20] 시작 👉 회의실 2개 필요 (+1)
16:
17:
18:
19:
20: [15, 20] 종료 👉 회의실 1개 필요 (-1)
21:
22:
23:
24:
25:
26:
27:
28:
29:
30: [0, 30] 종료 👉 회의실 0개 필요 (-1)

보시다시피 회의가 시작할 때 마다 새로운 회의실이 필요하고, 회의가 끝날 때 마다 기존에 쓰던 회의실이 필요가 없어집니다.

따라서 시작 시간과 종료 시간을 함께 묶어서 오름차순 정렬한다면 이 문제를 간단하게 해결할 수 있을 것입니다. 시작 시간에는 회의실이 하나 더 필요하기 때문에 +1을 덧붙이고, 종료 시간에는 회의실이 하나 덜 필요하기 때문에 -1을 덧붙이겠습니다.

intervals: [[0, 30], [5, 10], [15, 20]]
pairs: [(0, 1), (5, 1), (10, -1), (15, 1), (20, -1), (30, -1)]

자, 이제 시작 시간과 종료 시간이 통합된 배열을 루프 돌면서 덧붙인 +1 또는 -1을 모두 더해주기만 하면 되겠죠?

그럼 이 알고리즘을 파이썬으로 구현해볼까요?

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        pairs = []
        for start, end in intervals:
            pairs += [(start, 1), (end, -1)]
        pairs.sort()

        max_cnt, cnt = 0, 0
        for pair in pairs:
            cnt += pair[1]
            max_cnt = max(cnt, max_cnt)
        return max_cnt

입력 배열의 크기를 n이라고 했을 때, 이 풀이의 시간 복잡도는 O(nlog(n))입니다. 크기가 2n인 통합 배열을 정렬하는데 O(2nlog(2n))의 걸리는데 빅오 계산법으로 O(nlog(n))이 되기 때문입니다. 반면에 공간 복잡도는 통합 배열이 2n의 추가 공간을 필요로 하므로 O(n)이 되겠습니다.

마치면서

3가지 풀이 방법 모두 어느 정도 직관(intuition)을 요하는 쉽지 않은 문제였는데요. 이러한 직관은 코딩 문제를 많이 푸시다보시면 자연스럽게 길러지므로 한 번에 이해가 되지 않으시더라도 좌절하시지 않으셨으면 좋겠습니다. 복잡도는 동일하기 때문에 이 중에서 한 가지 방법으로만 풀 수 있으시다면 큰 지장은 없을 것입니다.

이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 Meeting Rooms를 풀어보시라고 추천드립니다. 코딩 테스트에서 구간을 어떻게 다루는지에 대해서 더 공부하고 싶으시다면 관련 게시물을 참고 바랄께요.