Python으로 구간 목록의 총 고유 지속 시간 계산하기

문제 소개

각 요소가 닫힌 구간 [start, end]를 나타내는 구간 목록이 주어졌다고 가정해 보겠습니다. 여기서 목표는 이 구간들이 중복 없이 실제로 덮는 총 고유 지속 시간(total unique duration), 즉 커버되는 전체 길이를 구하는 것입니다.

예를 들어 입력이 [[2, 11], [13, 31], [41, 61]]이라면 결과는 50입니다. 각 구간의 길이는 각각 (11 − 2 + 1) = 10, (31 − 13 + 1) = 19, (61 − 41 + 1) = 21이고, 세 구간이 서로 겹치지 않으므로 전체 합은 10 + 19 + 21 = 50이 됩니다.

접근 방식: 정렬 후 구간 병합

이 문제는 정렬(Sort) 후 구간 병합(Merge Intervals) 기법으로 효율적으로 해결할 수 있습니다. 처리 순서는 다음과 같습니다.

구간 목록이 비어 있으면 0을 반환합니다.
구간 목록을 시작 좌표 기준으로 오름차순 정렬합니다.
첫 번째 구간을 현재 구간 [start, end]로 설정하고 누적 변수 ans를 0으로 초기화합니다.
정렬된 목록의 각 구간 (s, e)에 대해 다음을 검사합니다.
- s > end인 경우: 현재 구간이 새 구간과 분리되어 있으므로, 지금까지의 구간 길이 (end − start + 1)를 ans에 더한 뒤 start와 end를 새 구간 값으로 갱신합니다.
- 그 외의 경우(겹치거나 인접): 두 구간을 하나로 합쳐 end를 max(end, e)로 확장하여 중복이 한 번만 계산되도록 합니다.
반복이 끝나면 마지막으로 남아 있는 구간의 길이 (end − start + 1)를 ans에 더합니다.
ans를 반환합니다.

Python 구현 코드

class Solution:
    def solve(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        start, end = intervals[0]
        ans = 0
        for s, e in intervals:
            if s > end:
                ans += end - start + 1
                start = s
                end = e
            else:
                end = max(end, e)
        ans += end - start + 1
        return ans


ob = Solution()
intervals = [[2, 11], [13, 31], [41, 61]]
print(ob.solve(intervals))

실행 결과

입력:

[[2, 11], [13, 31], [41, 61]]

출력:

코드 동작 원리

위 예제의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.

정렬된 첫 구간 [2, 11]로 start = 2, end = 11이 초기화됩니다.
[13, 31]을 만나면 13 > 11이므로 현재까지의 길이 10을 ans에 더하고, 현재 구간을 [13, 31]로 교체합니다.
[41, 61]을 만나면 41 > 31이므로 길이 19를 추가로 더해 ans = 29가 되고, 현재 구간은 [41, 61]로 바뀝니다.
루프 종료 후 마지막 구간 길이 21을 더해 최종 결과 50을 반환합니다.

만약 구간들이 서로 겹친다면(예: [[1, 5], [3, 8]]) else 블록에서 end가 max(end, e)로 확장되어 겹치는 부분이 중복 계산되지 않습니다. 이처럼 정렬된 순서대로 인접 구간을 하나로 합쳐 가며 길이를 누적하는 방식이 핵심입니다.

시간 및 공간 복잡도

시간 복잡도: 정렬에 O(n log n), 선형 순회에 O(n)이 소요되므로 전체 O(n log n)입니다.
공간 복잡도: 추가 자료구조 없이 상수 개의 변수만 사용하므로 O(1)입니다(정렬에 사용되는 내부 버퍼 제외).