겹치는 강의 시간표가 있을 때 필요한 최소 강의실 수 구하기

시간 구간 문제를 풀다 보면 "겹치는 구간이 최대 몇 개냐"를 묻는 경우가 자주 나옵니다.

겉으로는 단순히 시작 시간과 종료 시간이 주어진 것처럼 보이지만, 실제로는 동시에 몇 개가 진행 중인지 추적하는 문제인 경우가 많습니다.

이번 글에서는 여러 강의 일정이 주어졌을 때, 모든 강의를 문제없이 진행하려면 최소 몇 개의 강의실이 필요한지 구하는 방법을 정리해보겠습니다.

문제

여러 강의의 시간 구간이 배열로 주어집니다.

각 원소는 다음처럼 (start, end) 형태입니다.

(시작 시간, 종료 시간)

강의 시간이 서로 겹치면 같은 강의실을 사용할 수 없습니다.

이때 모든 강의를 배정하기 위해 필요한 최소 강의실 수를 구하세요.

예시

[(30, 75), (0, 50), (60, 150)]

이 경우를 시간 순서로 생각해보면:

• (0, 50) 강의가 먼저 시작
• (30, 75) 강의가 시작될 때 첫 번째 강의가 아직 끝나지 않음
• 따라서 이 시점에는 강의실이 2개 필요
• (60, 150) 강의가 시작될 때는 (0, 50)이 끝났으므로 다시 2개면 충분

따라서 정답은 다음과 같습니다.

2

처음 떠오르는 생각

가장 단순한 방법은 모든 강의 쌍을 비교해서 겹치는지 확인하는 것입니다.

하지만 강의가 많아지면 모든 쌍을 비교하는 방식은 비효율적입니다.

우리가 진짜 알고 싶은 것은 이것입니다.

어떤 순간에 동시에 진행 중인 강의가 몇 개인가?

즉, 구간을 직접 다 비교하기보다 시간 흐름에 따라 현재 진행 중인 강의 수를 세는 쪽이 더 자연스럽습니다.

핵심 아이디어

시작 시간 배열과 종료 시간 배열을 따로 정렬합니다.

예를 들어:

intervals = [(30, 75), (0, 50), (60, 150)]

이면

starts = [0, 30, 60]
ends   = [50, 75, 150]

처럼 나눌 수 있습니다.

이제 시작 시간을 앞에서부터 보면서:

• 다음 강의 시작 시간이 가장 빠른 종료 시간보다 빠르면
  • 새 강의실이 하나 더 필요
• 그렇지 않으면
  • 가장 빨리 끝나는 강의실을 재사용 가능

이 과정을 반복하면 됩니다.

코드

def min_rooms(intervals):
    if not intervals:
        return 0

    starts = sorted(start for start, end in intervals)
    ends = sorted(end for start, end in intervals)

    used_rooms = 0
    max_rooms = 0
    end_index = 0

    for start in starts:
        while end_index < len(ends) and ends[end_index] <= start:
            used_rooms -= 1
            end_index += 1

        used_rooms += 1
        max_rooms = max(max_rooms, used_rooms)

    return max_rooms

코드 해설

1. 빈 입력 처리

if not intervals:
    return 0

강의가 하나도 없으면 강의실도 필요 없습니다.

2. 시작 시간과 종료 시간 분리

starts = sorted(start for start, end in intervals)
ends = sorted(end for start, end in intervals)

시작 시간끼리, 종료 시간끼리 따로 정렬합니다.

이렇게 하면 "다음 시작"과 "가장 빠른 종료"를 비교하기 쉬워집니다.

3. 현재 사용 중인 강의실 수 추적

used_rooms = 0
max_rooms = 0
end_index = 0

• used_rooms는 현재 사용 중인 강의실 수
• max_rooms는 지금까지 필요한 최대 강의실 수
• end_index는 가장 빨리 끝나는 강의를 가리키는 포인터

4. 새 강의 시작 전에 끝난 강의 정리

while end_index < len(ends) and ends[end_index] <= start:
    used_rooms -= 1
    end_index += 1

현재 시작 시간보다 먼저 끝난 강의는 이제 강의실을 비웠다고 볼 수 있습니다.

그래서 사용 중인 강의실 수를 줄입니다.

여기서 <=를 쓰는 이유는:

어떤 강의가 50에 끝나고
다음 강의가 50에 시작하면
같은 강의실을 재사용할 수 있기 때문

입니다.

5. 현재 강의 배정

used_rooms += 1
max_rooms = max(max_rooms, used_rooms)

현재 시작하는 강의는 강의실 하나를 차지합니다.

그 뒤, 지금까지 중 가장 많이 필요했던 강의실 수를 갱신합니다.

예제로 따라가기

입력:

[(30, 75), (0, 50), (60, 150)]

정렬:

starts = [0, 30, 60]
ends   = [50, 75, 150]

시작 시간 0

아직 끝난 강의가 없습니다.

used_rooms = 1
max_rooms = 1

시작 시간 30

가장 빠른 종료 시간은 50인데 아직 안 끝났습니다.

used_rooms = 2
max_rooms = 2

시작 시간 60

종료 시간 50은 이미 지났으므로 강의실 하나를 반납합니다.

used_rooms = 1

그다음 현재 강의를 배정합니다.

used_rooms = 2
max_rooms = 2

최종 정답은 2입니다.

복잡도

정렬 때문에 시간 복잡도는 O(N log N)입니다.

추가로 시작 시간 배열과 종료 시간 배열을 만들기 때문에 공간 복잡도는 O(N)입니다.

왜 이 방식이 좋은가?

이 문제의 핵심은 각 강의가 어떤 방을 쓰는지 직접 기록하는 것이 아닙니다.

우리는 오직 다음만 알면 됩니다.

현재 동시에 진행 중인 강의 수

필요한 최소 강의실 수는 결국 동시에 열리는 강의 수의 최댓값과 같기 때문입니다.

즉, 방 번호를 배정하는 문제처럼 보여도 실제로는 겹치는 구간 수의 최대값을 구하는 문제입니다.

헷갈리기 쉬운 부분

1. 겹치는 쌍의 개수를 세는 문제가 아니다

두 강의가 겹치는지 하나씩 세는 것이 아닙니다.

중요한 것은 어떤 시점에 동시에 몇 개가 열리는지입니다.

예를 들어 세 강의가 한 시점에 모두 겹치면 강의실은 3개가 필요합니다.

2. 종료 시간과 시작 시간이 같으면 같은 방 사용 가능

(0, 50)
(50, 100)

이 두 강의는 겹치지 않습니다.

첫 번째 강의가 끝나자마자 두 번째 강의가 시작하므로 같은 강의실 하나로 충분합니다.

그래서 조건을 비교할 때 ends[end_index] <= start를 씁니다.

3. 힙으로도 풀 수 있다

이 문제는 최소 힙으로도 자주 풉니다.

현재 사용 중인 강의실의 종료 시간을 힙에 넣고, 가장 빨리 끝나는 종료 시간과 다음 시작 시간을 비교하는 방식입니다.

하지만 시작/종료 배열을 따로 정렬하는 방식도 아이디어가 단순해서 이해하기 좋습니다.

정리

이번 문제는 여러 강의 구간이 주어졌을 때, 모든 강의를 진행하려면 최소 몇 개의 강의실이 필요한지 구하는 문제입니다.

핵심은 다음 한 줄로 요약할 수 있습니다.

필요한 최소 강의실 수 = 동시에 진행 중인 강의 수의 최댓값

이를 위해 시작 시간과 종료 시간을 따로 정렬하고, 현재 사용 중인 강의실 수를 시간 흐름에 따라 갱신하면 됩니다.

정리하면 흐름은 다음과 같습니다.

시작 시간 정렬
종료 시간 정렬
-> 시작 전에 끝난 강의실 반납
-> 현재 강의 배정
-> 최대 동시 진행 수 갱신

시간 구간 문제를 볼 때 "방을 몇 개 배정할까?"로 보기보다 "겹치는 개수가 최대 몇 개일까?"로 바꾸면 더 잘 풀리는 경우가 많습니다.