Insert an Interval

intervals is a list of [start, end] pairs sorted by start, where no two intervals overlap or touch. Write insert_interval(intervals, new) that adds the interval new and returns the updated list, still sorted and without overlaps.

If new overlaps or touches any intervals (sharing an end point counts as touching), merge them all into one interval. Return a new list of [start, end] lists.

Examples

insert_interval([[1, 3], [6, 9]], [2, 5])
# returns [[1, 5], [6, 9]]

insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])
# returns [[1, 2], [3, 10], [12, 16]]

insert_interval([], [5, 7])
# returns [[5, 7]]

In the second example [4, 8] overlaps [3, 5], [6, 7] and [8, 10], and all four merge into [3, 10].

Constraints

• 0 <= len(intervals) <= 10,000
• start <= end for every interval, including new
• Values are between -10**6 and 10**6