57. 插入区间

https://leetcode-cn.com/problems/insert-interval/

解法一：

先找交叠的起始，再找交叠的终止。注意处理边界情况 至于为何要在第二次while中每次更新？因为插入段与原序列的元素区间可能存在包含关系，这样可以避免遗漏

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:        
        n = len(intervals)
        if n == 0: #序列为空，直接插入返回
            return [newInterval]
        res = []
        i = 0
        #处理new之前的非交叠段，直接加入res
        while i < n and newInterval[0] > intervals[i][1]:
            res.append(intervals[i])
            i += 1
        #此时进入交叠段
        #走出交叠段之前，每段合并一次
        while i < n and newInterval[1] >= intervals[i][0]:
            newInterval = [min(intervals[i][0], newInterval[0]), \
                            max(intervals[i][1], newInterval[1])]
            i += 1
        #将合并后的交叠段写入
        res.append(newInterval)     
        #剩下的非交叠段，直接写入
        for i in range(i, n):
            res.append(intervals[i])
        return res