DIY: Insert Interval

Problem statement

For this problem, you are given a list of non-overlapping intervals, and you need to insert another interval into the list. The output should contain a list of mutually exclusive intervals.

Input

The function has two inputs. The first input is a list of lists representing the list of intervals. The nested lists contain two integers representing the starting and ending time of the intervals. The second input is a list of two integers representing the new interval to be inserted. The following is an example input:

[[1, 3], [4, 5], [7, 9], [9, 15], [10, 14]] 
[2, 8]

Output

The output is the list of intervals after inserting the new interval. The following is an example output:

[[1, 9], [9, 15], [10, 14]]