57. Insert Interval

# Medium

想尽所有的可能性太复杂了，简化思想，将这个区间分成三部分，第一部分在newInterval之前，没有任何重叠，加入到res里，第二部分不断更新newInterval的起始位置，加入到res里，第三部分把剩余的加入到res里

Key idea: how to update newInterval?

view each small interval and update newInterval[1] with max(interval[cur][1], newInterval[1])

我觉得最难的是想出来更新区间时的while的限制条件

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        cur = 0
        n = len(intervals)
        # add all non-overlap intervals into res
        while cur < n and intervals[cur][1] < newInterval[0]:
            res.append(intervals[cur][:])
            cur += 1
            
        # find the new interval
        while cur < n and newInterval[1] >= intervals[cur][0]:
            newInterval[0] = min(intervals[cur][0], newInterval[0])
            newInterval[1] = max(intervals[cur][1], newInterval[1])
            cur += 1
        res.append(newInterval[:])
            
        while cur < n:
            res.append(intervals[cur][:])
            cur += 1
            
        return res