각 구간이 [시작, 끝] 형태로 표현되는 구간(interval) 목록이 주어졌다고 가정해 보겠습니다. 이때 서로 겹치는 구간들을 자유롭게 병합하여 만들 수 있는 가장 긴 구간의 길이를 구하는 것이 목표입니다.
예를 들어 입력이 [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]]라고 해보겠습니다. [1, 6]과 [4, 9]는 서로 겹치므로 하나로 합칠 수 있으며, 병합된 구간 [1, 9]의 길이는 9입니다. 따라서 출력은 9가 됩니다.
알고리즘 접근 방식
이 문제는 정렬 후 순차적 병합 전략으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 구간 목록 정렬: 모든 구간을 시작 시간 기준으로 오름차순 정렬합니다.
- 초기화: 첫 번째 구간을 현재 병합 구간(union)으로 삼고, best 값을 해당 구간의 길이(끝 − 시작 + 1)로 설정합니다.
- 순회하며 병합: 나머지 구간들의 시작 시간 s와 끝 시간 e를 검사합니다.
- s가 현재 병합 구간의 끝값 이하라면 두 구간이 겹치는 것이므로, 병합 구간의 끝값을 기존 끝값과 e 중 더 큰 값으로 갱신합니다.
- 그렇지 않다면 겹치지 않는 것이므로, 새로운 구간 [s, e]를 병합 구간으로 교체합니다.
- 최댓값 갱신: 매 반복마다 best를 현재 병합 구간의 길이와 비교하여 더 큰 값으로 갱신합니다.
- 결과 반환: 모든 구간을 처리한 뒤 best를 반환합니다.
구현 예제
class Solution:
def solve(self, intervals):
intervals.sort()
union = intervals[0]
best = union[1] - union[0] + 1
for s, e in intervals[1:]:
if s <= union[1]:
union[1] = max(union[1], e)
else:
union = [s, e]
best = max(best, union[1] - union[0] + 1)
return best
ob = Solution()
intervals = [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]]
print(ob.solve(intervals))
입력
[[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]]
출력
9
동작 원리 살펴보기
위 예제의 실행 흐름을 단계별로 살펴보면 다음과 같습니다.
- [1, 6]에서 시작하며 초기 best 값은 6입니다.
- [4, 9]는 [1, 6]과 겹치므로 병합되어 [1, 9]가 되고, best는 9로 갱신됩니다.
- [5, 6] 역시 [1, 9]에 완전히 포함되므로 병합 결과는 그대로 [1, 9]입니다.
- [11, 14]는 [1, 9]와 겹치지 않으므로 새로운 구간이 되지만, 길이가 4로 best(9)보다 작습니다.
- [16, 20]도 마찬가지로 길이가 5이므로 best는 여전히 9입니다.
최종적으로 가장 긴 병합 구간 [1, 9]의 길이인 9가 반환됩니다.
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후 순회와 병합 과정은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 병합 상태를 추적하는 데 상수 개의 변수만 사용하므로 추가 공간 복잡도는 O(1)입니다(정렬 알고리즘의 내부 동작은 제외).