[LeetCode/Python] 57. Insert Interval

📌 Problem

[LeetCode] 57. Insert Interval

📌 Solution

Solution

Idea

1. new interval과 겹치지 않는 앞부분을 그대로 결과에 추가

2. new interval과 겹치는 구간들은 하나로 병합

3. 남은 뒤쪽 interval들을 그대로 추가

Code

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []

        # 1) Add all intervals that do not overlap with the new interval (before it) 
        #    directly to the result
        i = 0
        n = len(intervals)
        while i < n and intervals[i][1] < newInterval[0]:
            ans.append(intervals[i])
            i += 1

        # 2) Merge all intervals that do overlap with the new interval into one
        start, end = newInterval
        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        ans.append([start, end])

        # 3) Append the remaining intervals after the merged interval
        while i < n:
            ans.append(intervals[i])
            i += 1

        return ans

Complexity

• Time: $O(n)$
• Space: $O(n)$ (결과 리스트)

Cf. Binary Search 이용하기?

Binary Search 를 이용하여 new interval 이 들어갈 자리를 찾는 방법이 더 효율적이지 않나?

정답은 그렇지 않다.

왜냐하면 어차피 병합 때문에 선형 스캔이 필요하기 때문!
newInterval이 몇 개의 interval과 겹치는지는 binary search 한 번으로는 알 수 없음.

[1,2] [3,5] [6,7] [8,10] [12,16]
             ↑
        newInterval = [4,9]

즉, 시작 위치는 BS로 찾을 수 있지만, 끝나는 위치는 겹침이 끝날 때까지 직접 확인해야 함. → 결국 $O(n)$ 스캔 발생

따라서, 시간 복잡도는 그대로 $O(n)$이므로 시작 위치를 Binary Search 로 찾아도 크게 효율적이지 않다.