[DSA][Intervals] 01. Insert Interval

LeetCode 57

 

01. Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.
You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.
Note that you don't need to modify intervals in-place. You can make a new array and return it.

 

 

[질문하기]

- intervals에 빈 배열이 들어올 수 있나요? YES

- newInterval이 invalid 할 가능성이 있나요?  NO

- 시작점과 끝점이 같은 interval도 있을 수 있나요? YES

 

[아이디어]

- interval과 newInterval의 위치 관계를 세 가지 경우로 나누어 처리한다.

 

 

[풀이 1] Greedy

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

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])
            else:
                newInterval = [
                    min(newInterval[0], intervals[i][0]),
                    max(newInterval[1], intervals[i][1]),
                ]
        res.append(newInterval)
        return res

intervals는 시작 시점 기준으로 정렬되어 있으므로, 앞에서부터 순차적으로 newInterval과 비교하면서 적절한 위치를 찾아준다.

 

1) newInterval이 현재 interval과 겹치지 않고 완전히 왼쪽에 있는 경우

newInterval을 결과 리스트에 추가하고, 이후의 남은 interval을 모두 붙여서 반환한다.

 

2) newInterval이 현재 interval과 겹치지 않고 완전히 오른쪽에 있는 경우

현재 interval을 결과 리스트에 그대로 삽입한다.

 

3) newInterval과 현재 interval이 겹치는 경우

두 interval 중 더 작은 start 값과 더 큰 end 값으로 newInterval을 갱신한다.

 

첫 번째 케이스에 해당하지 않는 경우, for문을 다 돌고 나서도 newInterval이 삽입되지 않고 남게 되므로, 마지막에 잊지 않고 append 해준다.

 

 

⏱️ 시간복잡도

배열을 한 번만 순회하며 연산을 수행하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

추가적으로 사용하는 공간 없이 결과를 담기 위한 배열만을 사용하므로 공간 복잡도는 O(n)이다.