Insert Interval
Medium · intervals
You are given a list intervals of closed ranges [start, end] of whole numbers (both ends included). The list is already sorted by start, and no two ranges in it share a number.
You are also given one more range, new_interval. Add it to the list. If it shares at least one number with any existing range, those ranges and the new one must be fused into a single range that covers all of them, so that afterwards no two ranges in the list share a number.
Return the resulting list, sorted by start. For example, [1, 2] and [2, 5] share the number 2 and become [1, 5], but [1, 2] and [3, 4] share nothing and stay separate. The list may be empty.
Examples
Example 1
Input: intervals = [[1, 3], [6, 9]], new_interval = [2, 5]
Output: [[1, 5], [6, 9]]
[2, 5] shares the numbers 2 and 3 with [1, 3], so the two fuse into [1, 5]. [6, 9] is untouched.
Example 2
Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new_interval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
[4, 8] reaches into [3, 5], [6, 7] and [8, 10], so all four fuse into [3, 10].
Example 3
Input: intervals = [], new_interval = [5, 7]
Output: [[5, 7]]
With nothing to fuse with, the new range is the whole answer.
Constraints
- 0 <= len(intervals) <= 10^4
- intervals[i] has exactly two numbers, start and end, and new_interval does too
- -10^5 <= start <= end <= 10^5 for every range, including new_interval
- intervals is sorted by start, and for each i, intervals[i][1] < intervals[i + 1][0]