Description
You are given an array of non-overlapping intervals sorted by start time. Insert a new interval into the intervals (merge if necessary). Return the resulting array of intervals, still sorted and non-overlapping.
Examples
Input:
intervals = [[1,3],[6,9]], newInterval = [2,5]Output:
[[1,5],[6,9]]Explanation:
[2,5] overlaps with [1,3], so merge to [1,5].
Input:
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]Output:
[[1,2],[3,10],[12,16]]Explanation:
[4,8] overlaps with [3,5], [6,7], [8,10].
Input:
intervals = [[2,4],[7,9],[11,15]], newInterval = [0,1]Output:
[[0,1],[2,4],[7,9],[11,15]]Explanation:
The new interval [0,1] doesn't overlap with any existing intervals and comes before all of them, so it's inserted at the beginning of the array.
Constraints
- •
0 ≤ intervals.length ≤ 10⁴ - •
intervals[i].length == 2 - •
0 ≤ start ≤ end ≤ 10⁵