You are given an array of non-overlapping intervals sorted by start time.
Insert newInterval into the list and merge intervals where necessary so the final result stays sorted and non-overlapping.
Examples
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]]
Constraints
- 0 <= intervals.length <= 10,000
- intervals[i].length == 2
- Intervals are sorted and non-overlapping.