Given a list of non-overlapping intervals sorted by start time, insert a new interval, merging with existing intervals if they overlap. Return the resulting sorted list of non-overlapping intervals.
Input
intervals: an array of [start, end] pairs, sorted by start, with no overlaps
newInterval: a single [start, end] pair to insert
Output
The updated list of non-overlapping intervals, sorted by start.
Examples
Example 1
Inputintervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output[[1, 5], [6, 9]]
Example 2
Inputintervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output[[1, 2], [3, 10], [12, 16]]
Constraints
intervals is sorted by start time.
start <= end for every interval.