57. Insert Interval

这道题基本上也就是loop一遍，然后对于每一个interval 分三种情况，在start 左边，在end 右边，和当前的start， end 相交。前两种情况直接加入res，最后一种情况扩展start和end

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not intervals:
            return [newInterval]
        res = []
        start = newInterval.start
        end = newInterval.end
        
        if end < intervals[0].start:
            return [newInterval] + intervals
        if start > intervals[-1].end:
            return intervals + [newInterval]
        
        i = 0
        found = False
        while i < len(intervals):
            if intervals[i].end < start:
                res.append(intervals[i])
            elif intervals[i].start > end:
                if not found:
                    res.append([start, end])
                    found = True
                res.append(intervals[i])
            else:
                start = min(start, intervals[i].start)
                end = max(end, intervals[i].end)
            
            i += 1
        
        if not found:
            res.append([start, end])
        return res