겹치지 않는(non-overlapping) 간격들의 리스트가 있다고 가정해 보겠습니다. 이 간격들은 종료 시간을 기준으로 정렬되어 있습니다. 여기에 또 다른 간격인 target이 주어졌을 때, target을 기존 간격들과 병합한 후에도 전체 간격 리스트가 여전히 겹치지 않고 정렬된 상태를 유지하도록 최종 결과를 구하는 것이 이번 문제입니다.
예를 들어, 입력이 intervals = [[1, 15], [25, 35], [75, 90]], target = [10, 30]이라면 출력은 [[1, 35], [75, 90]]가 됩니다. target [10, 30]이 기존 간격 [1, 15] 및 [25, 35]와 겹치기 때문에 이 세 개가 하나의 간격 [1, 35]로 병합되고, [75, 90]은 그대로 유지됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- target을 간격 리스트(iv)의 끝에 삽입합니다.
- iv를 시작 시간을 기준으로 정렬합니다.
- 첫 번째 간격을 포함하는 새로운 리스트 res를 생성합니다.
- i := 1로 초기화합니다.
- i가 iv의 크기보다 작은 동안 다음을 반복합니다.
- 만약 iv[i]의 시작 시간이 res의 마지막 간격의 종료 시간보다 작거나 같으면(즉, 두 간격이 겹치면), res의 마지막 간격의 종료 시간을 max(res 마지막 간격의 종료 시간, iv[i]의 종료 시간)으로 갱신합니다.
- 그렇지 않으면(겹치지 않으면), iv[i]를 res의 끝에 추가합니다.
- 반복이 끝나면 res를 반환합니다.
Python 예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, iv, target):
iv.append(target)
iv.sort(key=lambda x: x[0])
res = [iv[0]]
i = 1
while i < len(iv):
if iv[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], iv[i][1])
else:
res.append(iv[i])
i += 1
return res
ob = Solution()
intervals = [
[1, 15],
[25, 35],
[75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))
입력
[[1, 15],[25, 35],[75, 90]], [10, 30]
출력
[[1, 35], [75, 90]]
동작 원리 요약
이 알고리즘의 핵심은 target을 기존 리스트에 추가한 뒤 시작 시간 기준으로 정렬하면, 겹치는 모든 간격들이 인접하게 배치된다는 점입니다. 이후 한 번의 순회만으로 겹치는 간격들을 순차적으로 병합할 수 있으며, 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다. 이 방식은 캘린더 일정 관리, 회의실 예약 통합 등 실제 간격 병합 문제에 널리 활용됩니다.