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}}