[leetcode] Insert Interval

Insert Interval

생각한 방식

1. 예시를 보고 떠올린 방법. intervals를 큐로 만들고 newInterval의 start가 intervals[i]에 속했을 때 두 번 popleft를 한 뒤에 appendleft를 하는 방식.
   예) intervals = [[1,3],[6,9]], newInterval = [2,5]
   ⇢ intervals 중간에 있는 값을 바꾸기 어려움.
   ⇢ newInterval = [0,5]일 때 처리할 수 없음.
2. 해당하는 구간을 True로 저장하는 변수를 만드는 방법
   예) checkInRange = [F, T, T, T, T, T, T, F, F, T]
   ⇢ [2,5]와 [6,9]처럼 숫자가 앞뒤로 붙어있을 때 분리시킬 방법이 없음.

풀잇법

그림을 그리면 3가지 경우를 쉽게 떠올릴 수 있다.

1. newInterval[1] < interval[i][0]

newInterval과 interval[i]이 겹치지 않기 때문에 result에 newInterval을 그대로 넣어주면 된다.

2. newInterval[0] > interval[i][1]
   
   이것도 둘이 겹치지 않는다. 이때는 result에 interval[i]를 넣어준다.

3. 겹칠 때
   
   [min(starts), max(starts)]를 하면 된다.

코드

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        
        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                result.append(newInterval)
                return result + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                result.append(intervals[i])
            else:
                newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        
        result.append(newInterval)
        return result

참고 자료

NeetCode