Slot a New Range In
MediumIntervals
Problem
A booking system stores reserved hours as ranges: closed intervals [start, end], sorted by start and pairwise disjoint (no two share a point).
A new reservation newRange arrives. Insert it so the list stays sorted and disjoint, merging it with every existing range it shares at least one point with. Return the updated list.
Example 1
- Input:
- ranges = [[1, 3], [6, 9]], newRange = [2, 5]
- Output:
- [[1, 5], [6, 9]]
[2, 5] overlaps [1, 3]; it does not reach 6.
Example 2
- Input:
- ranges = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newRange = [4, 8]
- Output:
- [[1, 2], [3, 10], [12, 16]]
[4, 8] touches [3, 5], [6, 7] and [8, 10], which all collapse into [3, 10].
Constraints
- 0 ≤ ranges.length ≤ 10^5
- ranges is sorted by start and pairwise disjoint
- 0 ≤ start ≤ end ≤ 10^9 for every range, including newRange
Hint
Show the first hint
The list is already sorted and disjoint. Can you avoid sorting again?
Walkthrough
How to approach it
01Clarify before coding
- Is the input sorted and disjoint? Yes, which is what makes a linear solution possible.
- Do touching ranges merge? Yes, sharing a single point such as [1, 2] and [2, 6] counts.
- Can the list be empty? Yes → return [newRange].
02Brute force
Append newRange, sort everything and run a general merge.
Cost: O(n log n) time: correct, but it throws away the order the input already gives you.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.