Intervals + Greedy
Insert into a sorted sweep
Why it matters
Booking systems and address allocators often receive one new range after their existing ranges have already been sorted and cleaned. Sorting the unchanged history again adds latency without adding information. The new interval must be integrated in one pass while preserving sorted, non-overlapping output.
Example
Insert Interval
intervals is sorted and disjoint. Insert newInterval and merge if needed. Return the new disjoint list.
- Input
- intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
- Output
- [[1, 2], [3, 10], [12, 16]]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Insert Interval
intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]→[[1, 2], [3, 10], [12, 16]]
The baseline, Append, then merge again, is O(n log n) · O(n). The better model below keeps this exact input and removes that bottleneck.
Appending [4, 8] to the five sorted intervals and brute re-merging sorts all six again. Use their existing order: copy [1, 2], absorb the contiguous run [3, 5] through [8, 10] into [3, 10], then copy [12, 16].
For [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] and new [4, 8], [1, 2] ends before 4, so copy it unchanged. [3, 5] overlaps and widens the active range to [3, 8].
[6, 7] fits inside [3, 8], and [8, 10] touches its end, widening it to [3, 10]. The next interval [12, 16] starts after 10, so append the widened range and copy [12, 16]. The result is [[1, 2], [3, 10], [12, 16]].
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.