여러 영화의 상영 시간이 담긴 구간(interval) 목록이 주어졌을 때, 이 영화들을 겹치는 시간 없이 모두 상영하기 위해 필요한 최소 영화관 수를 구하는 문제를 살펴보겠습니다. 각 구간은 서로 겹칠 수 있으며, 동시에 상영되는 영화가 많아질수록 더 많은 영화관이 필요합니다.
문제 예시
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
intervals = [[20, 65], [0, 40], [50, 140]]
이 경우 출력은 2가 됩니다. 그 이유는 다음과 같습니다.
- [20, 65]와 [0, 40]은 시간이 겹치므로 서로 다른 영화관에서 상영해야 합니다.
- [20, 65]와 [50, 140] 역시 겹칩니다.
- 하지만 [0, 40]과 [50, 140]은 겹치지 않으므로 같은 영화관을 공유할 수 있습니다.
따라서 최소 2개의 영화관이면 모든 영화를 상영할 수 있습니다.
해결 접근 방식: 스윕 라인(Sweep Line) 알고리즘
이 문제는 스윕 라인 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 영화의 시작 시간에는 영화관 사용 수가 +1 증가하고, 종료 시간에는 -1 감소한다고 생각합니다.
- 모든 시작/종료 이벤트를 하나의 리스트에 모은 뒤 시간 순으로 정렬합니다.
- 이벤트를 순회하면서 누적합(현재 사용 중인 영화관 수)을 계산하고, 그중 최댓값이 곧 필요한 최소 영화관 수입니다.
정렬 시 주의할 점은, 시작과 종료가 같은 시간에 발생하면 종료 이벤트(-1)를 먼저 처리하는 것이 안전하다는 것입니다. 파이썬의 튜플 정렬에서는 -1이 1보다 앞에 오므로 자연스럽게 처리됩니다.
구현 코드
다음은 위 알고리즘을 파이썬으로 구현한 예제입니다.
class Solution:
def solve(self, intervals):
t = []
for a, b in intervals:
t.append((a, 1)) # 영화 시작: +1
t.append((b, -1)) # 영화 종료: -1
ans = count = 0
for x, d in sorted(t):
count += d
ans = max(ans, count)
return ans
ob = Solution()
intervals = [[20, 65], [0, 40], [50, 140]]
print(ob.solve(intervals))입력
[[20, 65], [0, 40], [50, 140]]
출력
2
복잡도 분석
- 시간 복잡도: O(N log N) — 이벤트 정렬에 지배적으로 소요됩니다. (N은 구간의 개수)
- 공간 복잡도: O(N) — 각 구간마다 두 개의 이벤트를 저장합니다.
이 방법은 회의실 배정(Meeting Rooms II), 플랫폼 최소 개수 구하기 등 유사한 구간 겹침 문제에도 널리 활용되는 패턴이므로, 응용 문제를 함께 연습해 보시길 권장합니다.