The problem
Given non-overlapping intervals sorted by start, insert a new interval and merge wherever needed so the list stays sorted and non-overlapping.
Input: [1,2] [3,5] [6,7] [8,10] [12,16], new [4,8] Output: [1,2] [3,10] [12,16]
Picture it
Picture a calendar of bookings. Bookings that end before the new one starts stay as they are. Bookings that overlap the new one get melted into it (its start becomes the earliest start, its end the latest end). Bookings starting after it ends stay as they are.
How to recognise it
- The input is a list of intervals that are already sorted and do not overlap, and one new interval arrives.
- The output must stay sorted and non-overlapping, so anything the new interval touches has to be merged into it.
- Because the list is sorted, it splits into three runs: intervals that end before the new one starts, intervals that overlap it, and intervals that start after it ends. Each run is contiguous.
- Up to 10^4 intervals, and the sorting has already been done for you, so one pass is the target.
- Here intervals that only touch (
[1, 2]and[2, 3]) count as overlapping and are merged.
Start with brute force
Ignore the existing order: add the new interval, sort everything, and merge overlapping neighbours, exactly as in Merge Intervals.
def insert_brute(intervals, new):
allv = sorted(intervals + [new])
out = [list(allv[0])]
for start, end in allv[1:]:
if start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return out
Time is O(n log n) for the sort and space O(n). For 10^4 intervals that is still fast. The waste is the sort itself: the list was sorted and disjoint before, and only one interval is out of place.
From brute force to the idea
- Find the waste. Sorting re-orders n intervals that are already in order. Only the region around the new interval can change.
- Phase 1: copy what ends before. While
intervals[i][1] < new[0], the interval finishes before the new one starts, so it is copied unchanged. The test is strict: an interval ending exactly atnew[0]touches it and must be merged. - Phase 2: absorb what overlaps. While
intervals[i][0] <= new[1], the interval starts before the new one ends. Since phase 1 already skipped everything ending earlier, it must overlap. Stretchnewto the smaller start and the larger end. Several intervals can be swallowed in a row. - Add the merged interval. After phase 2,
newcovers everything it touched. Append it once. - Phase 3: copy the rest. Every remaining interval starts after
newends, soout.extend(intervals[i:])adds them in order.
This is the key idea: in a sorted list the new interval meets one contiguous run, so walk once, keeping, merging, then keeping again.
The key idea
Three phases: before, overlapping (merge), after. O(n).
Python solution
def insert(intervals, new):
out, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < new[0]:
out.append(intervals[i]); i += 1 # ends before: keep
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]), # overlaps: absorb it
max(new[1], intervals[i][1])]
i += 1
out.append(new)
out.extend(intervals[i:]) # starts after: keep
return outIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n log n): sorting all intervals again | O(n): the sorted copy and the output |
| Three phases (shown code) | O(n): the index i only moves forward, each interval is looked at once | O(n): the output list; O(1) besides it |
Edge cases
- Empty list (
[], new[5, 7]): both loops are skipped and the result is[[5, 7]]. - New interval before everything (
[[3, 5]], new[1, 2]): phase 1 copies nothing,[1, 2]is added first, then[3, 5]. - New interval after everything (
[[1, 2]], new[4, 5]): phase 1 copies[1, 2], then[4, 5]is appended. - Touching intervals (
[[1, 2], [5, 6]], new[2, 3]): merged into[[1, 3], [5, 6]]. - Swallowing many (
[[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new[4, 8]): returns[[1, 2], [3, 10], [12, 16]]. - New interval inside one (
[[1, 10]], new[3, 4]): returns[[1, 10]]. - The input is not changed:
newis replaced by a fresh list, not edited, butoutshares the untouched interval lists with the input.
Common mistakes
- Using
<=in phase 1, which keeps an interval that only touches the new one separate instead of merging it. - Appending the merged interval inside phase 2, once per absorbed interval, which creates duplicates.
- Comparing only with the first overlapping interval's end. The merged end is
max(new[1], intervals[i][1]), because the new interval may reach past several. - Forgetting phase 3, which drops every interval after the new one.
The intervals are now half-open ([a, b) contains a but not b), sorted and disjoint. Remove the range [x, y) from them and return what is left. For [[0, 2], [3, 4], [5, 7]] with [1, 6) removed, the answer is [[0, 1], [6, 7]]. Describe your approach, then write it if you like.
Compare with our answer
Still one pass over the sorted list. An interval that does not touch the cut is kept whole. One that does may leave a piece on the left (if it starts before x) and a piece on the right (if it ends after y), possibly both.
def remove_interval(intervals, cut):
x, y = cut
out = []
for a, b in intervals:
if b <= x or a >= y: # no overlap: keep whole
out.append([a, b])
else:
if a < x:
out.append([a, x]) # piece left of the cut
if b > y:
out.append([y, b]) # piece right of the cut
return out
Time O(n), space O(n) for the output.
A strong answer mentions: the no-overlap test for half-open intervals, the two possible leftover pieces, and that the output stays sorted without re-sorting.
1. A list of 10^4 sorted, non-overlapping free slots must be updated after a meeting removes part of that time. Which approach fits best?
The list is sorted, so the affected slots form one contiguous run and one pass handles it in O(n). Merging would combine time instead of removing it, and a minute array depends on the time range, not on n.
2. Why is the shown code O(n) rather than O(n log n)?
Three phases share one index that never goes back, so each interval is examined once. Phase 2 can absorb many intervals, and extend still copies the rest in O(n).
3. A learner changes phase 1 to intervals[i][1] <= new[0]. Which input now gives a wrong answer?
[1, 2] ends exactly where [2, 3] starts, so <= copies it in phase 1 and the result is [[1, 2], [2, 3], [5, 6]]. In the other inputs no interval ends exactly at the new start, so the two tests agree.
Score 60% or more and the lesson is marked complete.