57. Insert Interval
You maintain a tidy schedule: intervals is a list of closed ranges [start, end] that is already sorted by start and contains no overlaps. A new range new_interval = [start, end] now has to be added.
Write a function that receives intervals and new_interval and returns the schedule after the insertion — still sorted by start, still free of overlaps. If the new range collides with existing ones (including merely touching at an endpoint), all colliding ranges must be fused with it into a single range.
The original list may be empty, and the new range may land before everything, after everything, or swallow the entire schedule.
Example 1:
Input: intervals = [[1, 3], [6, 9]], new_interval = [2, 5]
Output: [[1, 5], [6, 9]]
Explanation: The new range [2, 5] overlaps [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]]
Explanation: [4, 8] reaches into [3, 5], covers [6, 7] entirely, and touches [8, 10], so those three fuse with it into [3, 10].
Constraints:
- 0 ≤ n ≤ 10⁴
- 0 ≤ start ≤ end ≤ 10⁹ for every interval
- intervals is sorted by start and its members do not overlap
Hints:
Every existing interval falls into exactly one of three buckets: entirely left of the new range (its end < new start), entirely right of it (its start > new end), or colliding with it.
The 'left' intervals pass through unchanged, then one fused interval, then the 'right' intervals — the input being sorted means those groups are contiguous.
Fusing is just min of the starts and max of the ends across the new range and everything it collides with.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: intervals = [[1, 3], [6, 9]], new_interval = [2, 5]
Expected output: [[1, 5], [6, 9]]