You're given an array of non-overlapping intervals sorted by start, where intervals[i] = [start, end], and one more interval, newInterval.
Insert newInterval so the list stays sorted and non-overlapping, merging intervals where necessary, and return the result. Intervals that touch at an endpoint count as overlapping.
Examples
Example 1
- Input
- intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
- Output
- [[1, 5], [6, 9]]
Example 2
- Input
- intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
- Output
- [[1, 2], [3, 10], [12, 16]]
- Why
- [4, 8] overlaps [3, 5], [6, 7] and [8, 10], so they merge into [3, 10].
Example 3
- Input
- intervals = [], newInterval = [5, 7]
- Output
- [[5, 7]]
Constraints
0 <= intervals.length <= 10^40 <= start <= end <= 10^5intervalsis sorted by start and has no overlaps.