Mid/SeniorArray
Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represents the start and the end of the i^th interval, and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that:
intervalsis still sorted in ascending order bystarti.intervalsstill does not have any overlapping intervals.- Overlapping intervals are merged if necessary.
Return intervals after the insertion.
Note that you do not need to modify intervals in-place. You can make a new array and return it.
Example 1
1---3
6-----9
2-----5
---
1-------5
6-----9Input
intervals = [[1,3],[6,9]], newInterval = [2,5]Output
[[1,5],[6,9]]The new interval [2,5] overlaps with [1,3], so they are merged into [1,5].
Example 2
1-2
3---5
6-7
8---10
12------16
4-------8
---
1-2
3-------------10
12------16Input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]Output
[[1,2],[3,10],[12,16]]Because the new interval [4,8] overlaps with [3,5], [6,7], and [8,10].
Constraints
0 <= intervals.length <= 10^4intervals[i].length == 20 <= starti <= endi <= 10^5intervalsis sorted bystartiin ascending order.newInterval.length == 20 <= start <= end <= 10^5