Meeting Rooms II

Q: Meeting Rooms II의 시간 복잡도는 무엇인가요?

두 가지 빠른 솔루션은 모두 O(n log n) 의 시간 복잡도로 실행됩니다. 힙 방식은 회의들을 정렬하고 회의마다 O(log n) 힙 연산을 한 번 수행합니다. 두 목록 방식은 두 번 정렬하고 O(n) 으로 한 번 순회합니다. 두 방식 모두 O(n) 의 추가 공간을 사용합니다. 각 시작 시점에 진행 중인 회의 수를 세는 방법은 O(n²) 입니다.

보통구간 힙 정렬

+10

회의 목록이 두 개의 배열로 주어집니다. 회의 i는 starts[i]부터 ends[i]까지 진행됩니다. 한 회의실에서는 한 번에 하나의 회의만 열 수 있으며, 회의실에서 다른 회의가 끝나는 바로 그 순간에 새로운 회의가 시작될 수 있습니다.

모든 회의를 수용할 수 있는 최소 회의실 수를 반환하는 minMeetingRooms라는 함수를 작성하세요.

함수

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

startsinteger-array: 각 회의의 시작 시간
endsinteger-array: 각 회의의 종료 시간은 시작 시간과 동일한 인덱스에 있습니다
반환값integer: 모든 회의를 수용할 수 있는 최소한의 회의실 수

제약 조건

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
회의는 정렬되어 있지 않습니다. 두 회의가 동일할 수도 있습니다.

예제

입력: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
출력: 3
설명: 시각 4에는 1부터 5까지, 2부터 6까지, 4부터 8까지의 회의가 모두 진행 중이므로 최소 3개의 회의실이 필요합니다. 3개면 충분합니다. 7부터 9까지의 회의는 5시에 비는 회의실을 사용합니다.

입력: starts = [0, 2, 3]ends = [10, 3, 5]
출력: 2
설명: 0부터 10까지의 회의는 내내 회의실 하나를 사용합니다. 2부터 3까지의 회의에는 두 번째 회의실이 필요하고, 3부터 5까지의 회의는 그 회의실이 비는 대로 사용하므로 2개의 회의실이면 충분합니다.

제출 시 숨은 테스트 +17개

후속 질문

정답에서 제시한 수보다 많은 회의실을 사용하지 않으면서 각 회의가 어느 회의실에 배정되는지도 말할 수 있나요?

풀이

필요한 회의실 수는 같은 시각에 진행 중인 회의의 최대 개수입니다. 각 시작 시각마다 진행 중인 회의를 세면 O(n²)에 구할 수 있습니다. 정렬을 이용하면 하루를 한 번 훑는 문제로 바뀝니다. 회의실이 비는 시각을 담은 최소 힙이나 시작 시각과 종료 시각을 정렬한 두 목록을 사용하면 O(n log n)에 답을 구할 수 있습니다.

각 시작 시점에 진행 중인 회의 수 세기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

어느 순간이든 진행 중인 각 회의에는 전용 회의실이 하나씩 필요합니다. 따라서 동시에 진행되는 회의 수가 가장 많을 때의 회의실 수만큼은 최소한 필요합니다. 그만큼이면 충분하기도 합니다. 시작 시간 순서대로 회의실을 배정하면, 모든 회의실이 사용 중일 때만 새 회의실이 필요하며, 이는 바로 그 순간 그 수만큼의 회의가 진행 중이라는 뜻입니다.

진행 중인 회의 수는 회의가 시작될 때만 늘어나므로, 가장 바쁜 순간은 어떤 회의가 시작되는 시점입니다. 각 회의 i에 대해 starts[j] ≤ starts[i] < ends[j]를 만족하는 회의 j의 수를 세면 됩니다. 이 회의들은 이미 시작했고 아직 끝나지 않았습니다. starts[i]와 정확히 같은 시점에 끝나는 회의는 세지 않습니다. 그 순간 회의실을 다시 사용할 수 있기 때문입니다.

첫 번째 예시에서는 시각 4에 1부터 5까지, 2부터 6까지, 4부터 8까지 진행되는 회의가 있습니다. 총 3개입니다. 시각 7에는 4부터 8까지와 7부터 9까지 진행되는 회의만 있습니다. 총 2개입니다. 최댓값은 3입니다.

n개의 회의 각각에 대해 n개의 회의를 모두 확인합니다. n = 5000이면 2,500만 번 확인하게 됩니다. C에서는 1초도 안 걸리지만 Python이나 R에서는 몇 초가 걸리며, n이 두 배가 될 때마다 확인 횟수는 네 배가 됩니다.

알고리즘

각 회의 i에 대해 running을 0으로 설정합니다.
각 회의 j에 대해 starts[j] ≤ starts[i] < ends[j]일 때 running에 1을 더합니다.
지금까지 확인한 running의 최댓값을 유지합니다.
그 최댓값을 반환합니다.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

회의실이 비는 시간의 최소 힙

핵심 아이디어

프런트 데스크 직원이 하듯 회의실을 배정하세요. 시작 시간 순서대로 회의를 살펴봅니다. 각 회의마다 가장 먼저 비는 회의실을 확인하세요. 회의가 시작할 때까지 그 회의실이 비면 해당 회의에 배정합니다. 그렇지 않으면 모든 회의실이 아직 사용 중이므로 새 회의실을 엽니다.

회의실 하나만 확인해도 안전합니다. 가장 먼저 비는 회의실이 아직 사용 중이면 다른 회의실도 모두 사용 중입니다. 비어 있다면 비어 있는 회의실은 어느 것이든 마찬가지입니다. 아직 남은 회의는 지금 이 시각이나 그 이후에 시작하므로, 지금 비어 있는 모든 회의실은 해당 회의가 시작될 때까지 계속 비어 있습니다.

회의실 중 가장 이른 빈 시각이 필요하며, 그 시각은 회의가 끝날 때마다 바뀝니다. 최소 힙은 회의실마다 종료 시각 하나를 저장하고 가장 작은 값을 꺼내 줍니다. 회의실을 재사용하면 종료 시각을 새 회의의 종료 시각으로 바꾸고, 회의실을 열면 새 종료 시각을 힙에 추가합니다. 첫 번째 예시에서 시작 시간순으로 정렬하면, 1부터 5까지는 [5]가 되고, 2부터 6까지는 [5, 6]이 되며, 4부터 8까지는 [5, 6, 8]이 됩니다. 7부터 9까지의 회의는 7 이전이나 7과 같은 시각에 끝나는 5를 찾아 대체하므로 [6, 8, 9]가 남습니다. 회의실은 세 개입니다.

정렬에는 O(n log n)이 들고, 각 회의마다 O(log n)의 힙 연산이 한 번 수행됩니다. Python의 heapq, Java의 PriorityQueue, greater를 사용하는 C++의 priority_queue, Reverse를 사용하는 Rust의 BinaryHeap, Go의 container/heap, PHP의 SplMinHeap을 사용하면 힙을 쓸 수 있습니다. 다른 언어에서는 배열로 직접 관리합니다. 인덱스 i의 부모는 (i-1)/2에 있으며, 값이 부모보다 작으면 위로 이동합니다.

알고리즘

각 회의의 시작 시간과 종료 시간을 짝지어 시작 시간 기준으로 정렬합니다.
각 회의에 대해 힙이 비어 있지 않고 가장 작은 종료 시간이 회의의 시작 시간과 같거나 이르면, 해당 종료 시간을 회의의 종료 시간으로 바꿉니다.
그렇지 않으면 회의의 종료 시간을 힙에 추가합니다. 새 회의실이 열립니다.
회의실마다 항목 하나씩 들어 있으므로 힙의 크기를 반환합니다.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

시작 시간과 종료 시간을 각각 정렬합니다

핵심 아이디어

힙은 어느 종료 시간이 어느 회의실에 속하는지 기억하지만, 답은 개수뿐입니다. 회의가 시작될 때 중요한 것은 어떤 회의가 그때까지 끝나 회의실을 비웠는지 여부뿐이며, 어떤 회의였는지는 중요하지 않습니다. 따라서 시작 시간과 종료 시간을 각각 별도의 목록으로 정렬한 뒤, 종료 시간 목록을 가리키는 포인터 ended를 두고 시작 시간 목록을 순회합니다.

시작 시간 순서대로 각각 살펴봅니다. 해당 시간이 endTimes[ended]보다 크거나 같으면 그때까지 회의가 끝난 것입니다. 그 회의실에 새 회의를 배정하고 ended를 다음으로 이동합니다. 그렇지 않으면 사용 중인 모든 회의실이 여전히 차 있으므로 rooms를 1 늘립니다. 각 시작 시간은 종료 시간 하나를 최대 한 번 사용합니다. 이는 힙에서 재사용한 회의실이 기존 종료 시간 하나를 새 종료 시간 하나로 바꾸는 것과 같습니다.

첫 번째 예제의 시작 시간은 1, 2, 4, 7이고 종료 시간은 5, 6, 8, 9입니다. 시작 시간 1, 2, 4는 모두 종료 시간 5보다 앞서므로 rooms는 3까지 늘어납니다. 시작 시간 7은 5보다 크거나 같으므로 그 회의실을 재사용하고 ended는 종료 시간 6으로 이동합니다. 답은 3입니다. 회의 시간이 맞닿을 때 같은 회의실을 공유하는 경우가 바로 ≥입니다. 두 번째 예제에서는 시작 시간 12가 종료 시간 12와 맞닿아 해당 회의실을 재사용합니다.

개수는 실제 최대치를 넘지 않습니다. rooms가 늘어날 때 다음 종료 시간은 아직 미래이므로, 그 순간 rooms개의 회의가 모두 진행 중입니다. 또한 실제로 해당 시작 시간 이전이나 그 시점에 끝난 회의가 회의실을 비운 경우에만 새 회의실을 열지 않으므로 최대치에 도달합니다. 정렬 두 번의 비용은 O(n log n), 순회는 O(n)이며, 정렬된 복사본에는 O(n)의 공간이 필요합니다.

알고리즘

시작 시간의 복사본과 종료 시간의 복사본을 정렬합니다.
rooms와 ended를 0으로 설정합니다.
각 시작 시간을 순서대로 확인하고, 해당 시간이 endTimes[ended]보다 늦거나 같으면 ended에 1을 더합니다. 회의가 비워진 방을 사용합니다.
그렇지 않으면 rooms에 1을 더합니다.
rooms를 반환합니다.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

함정과 경계 사례

대부분의 버그는 시간이 맞닿는 순간의 비교나 어떤 회의실을 확인하는지에서 발생합니다.

start ≥ end 대신 start > end를 확인하는 경우입니다. 그러면 회의가 회의실이 비는 순간 바로 그 방을 사용할 수 없어서, 10시부터 12시, 12시부터 14시, 14시부터 16시까지 이어지는 회의에 회의실 1개가 아니라 2개가 필요합니다.
가장 먼저 비는 회의실이 아니라 마지막으로 연 회의실을 확인하는 경우입니다. 1시부터 3시, 2시부터 10시, 4시부터 6시까지의 회의에서는 마지막으로 연 회의실이 10시까지 사용 중이므로, 첫 번째 회의실은 3시부터 비어 있는데도 세 번째 회의실을 열게 됩니다.
한 회의와 겹치는 회의의 최대 개수에 1을 더하는 경우입니다. 0시부터 10시까지의 회의는 2시부터 3시까지의 회의와 3시부터 5시까지의 회의와 겹치지만, 그 두 회의는 서로 겹치지 않으므로 회의실은 3개가 아니라 2개면 충분합니다.
정렬하는 두 가지 접근 방식을 혼동하는 경우입니다. 힙 방식에서는 시작 시간순으로 정렬하기 전에 각 종료 시간을 해당 시작 시간과 짝지어야 합니다. 두 목록을 사용하는 방식에서는 의도적으로 시작 시간과 종료 시간을 따로 정렬합니다.

자주 묻는 질문4

Meeting Rooms II의 시간 복잡도는 무엇인가요?

두 가지 빠른 솔루션은 모두 O(n log n)의 시간 복잡도로 실행됩니다. 힙 방식은 회의들을 정렬하고 회의마다 O(log n) 힙 연산을 한 번 수행합니다. 두 목록 방식은 두 번 정렬하고 O(n)으로 한 번 순회합니다. 두 방식 모두 O(n)의 추가 공간을 사용합니다. 각 시작 시점에 진행 중인 회의 수를 세는 방법은 O(n²)입니다.

min-힙은 왜 Meeting Rooms II 문제를 해결할까요?

회의를 시작 시간 순서대로 처리할 때 확인할 가치가 있는 유일한 회의실은 가장 먼저 비는 회의실입니다. 종료 시간을 저장하는 최소 힙을 사용하면 해당 회의실을 O(1)에 확인하고 O(log n)에 갱신할 수 있습니다. 모든 회의실이 사용 중일 때만 힙이 커지므로, 최종 크기는 필요한 최소 회의실 수입니다.

Meeting Rooms II를 힙 없이 풀 수 있을까요?

네. 시작 시간과 종료 시간을 별도의 두 목록으로 정렬하고, 종료 시간 목록의 포인터를 사용해 시작 시간 목록을 순회하세요. 시작 시간이 다음으로 사용되지 않은 종료 시간과 같거나 그 이후이면 회의실을 재사용하고, 그렇지 않으면 새 회의실을 사용합니다. 같은 아이디어를 스위프 라인으로 구현할 수도 있습니다. 각 회의를 시작 시점의 +1 이벤트와 종료 시점의 -1 이벤트로 바꾸고, 시간이 같으면 종료 이벤트를 시작 이벤트보다 먼저 처리한 다음, 누적 합계의 최댓값을 추적하세요.

한 번에 겹치는 회의가 가장 많은 경우와 답이 같나요?

맞습니다. 같은 시간에 진행되는 회의에는 서로 다른 회의실이 필요하므로, 적어도 그만큼의 회의실이 필요합니다. 시작 시간 순서대로 각 회의에 비어 있는 회의실을 배정하면 그보다 더 많은 회의실이 필요한 경우는 없으므로, 겹치는 회의의 최대 개수가 정답입니다.

Python

def minMeetingRooms(starts, ends):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

기대값

Meeting Rooms II

함수

제약 조건

예제

힌트

풀이

각 시작 시점에 진행 중인 회의 수 세기

회의실이 비는 시간의 최소 힙

시작 시간과 종료 시간을 각각 정렬합니다

함정과 경계 사례

자주 묻는 질문4

비슷한 문제