# https://leetcode.com/problems/insert-interval/
# 57. Insert Interval
# 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.
# Example 1:
# Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
# Output: [[1,5],[6,9]]
# Example 2:
# 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].

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