leet code 57 - Insert Interval

---

구간에 삽입하는 문제

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

 

시간복잡도 o(n) 

총 세가지의 경우가 발생한다. 1. 새로운구간의 마지막 값이이 현재 순회하고 있는 구간의 시작값보다 작은경우( 이는 그 순회하고 있는 구간의 뒤 값들에 대해선 더 볼 것도 없이, 겹쳐지는 구간이 발생하지 않는다. 따라서 바로 return

2. 새로운 구간의 시작값이, 순회하고 있는 구간의 마지막값보다 큰경우

순회하고 있는 값 append

3. 새로운 구간이 순회하고 있는 구간과 겹치는 경우.

1번째  if에서 새로운 구간의 마지막값이, 순회하고 있는 구간의 시작 값보다 작지는 않은지 검사한다.

만약작다면 그상태로 new interval을 append하고, res + intervals[i:]반환.

2번째 if문에서는 새로운 구간의 시작값이, 순회하고 있는 구간의 마지막값보다 큰지 검사한다. 

이후 해당 구간 append

3째 if문은 이미 겹쳐지는 경우로, 시작값과 마지막값을 max min연산을 통해, new interval을 만든다.

이후 res.append(newInterval) return.