57. Insert Interval

例

Input: 
    intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
    newInterval = [4,8]
    
Output: 
    [[1,2],[3,10],[12,16]]

Explanation: 
    Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10]

CODE

def insert(intervals, newInterval):
    left, right = [], []
    newStart = newInterval[0]
    newEnd = newInterval[1]
    for i in intervals:
        if i[1] < newStart:
            left.append(i)
        elif i[0] > newEnd:
            right.append(i)
        else:
            newStart = min(i[0], newStart)
            newEnd = max(i[1], newEnd)
    middle = [[newStart, newEnd]]
    return left + middle + right