题目
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
解题思路
分三个部分，先把在newInterval前面的区间加到结果里，再把与newInterval相交的区间进行合并，最后把余下的区间加到结果里
代码
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
while i < n and intervals[i][1] < newInterval[0]:
res.append(intervals[i])
i += 1
l, r = newInterval
while i < n and intervals[i][0] <= newInterval[1]:
l = min(l, intervals[i][0])
r = max(r, intervals[i][1])
i += 1
res.append([l, r])
res.extend(intervals[i:])
return res
