57. Insert Interval

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

非常巧妙的解法，分了三部分，左，右和中间merge 部分

三种情况：

1.新interval和merge interval 不相交且在merge interval左边

2.  新interval和merge interval不相交且在 merge interval右边

3. 新interval 和 merge interval相交，那么更新merge interval。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        start,end = newInterval
        left= []
        right = []
        for interval in intervals:
            if interval[1] < start:
                left.append(interval)
            elif interval[0] > end:
                right.append(interval)
            else:
                start = min(start,interval[0])
                end = max(end, interval[1])
        return left + [[start,end]] + right