Insert into a sorted list
Copy what ends before the new interval, absorb everything it overlaps, then copy the rest. About 12 minutes.
Three parts of the list
Imagine slotting a new meeting into a sorted calendar. Walk the list once. First, copy every interval that ends before the new one starts: they can't touch it.
Next, every interval that starts at or before the new one's end overlaps it, so absorb it by widening the new interval. Then add the widened interval and copy the rest unchanged.
result = []
start, end = added
i, n = 0, len(intervals)
while i < n and intervals[i][1] < start:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
result.append([start, end])
result.extend(intervals[i:])
return result[1, 2] ends before the new one starts at 4. It can't touch it: copy it.
Trace it
List [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new [4, 8]. [1, 2] ends before 4: copy. [3, 5], [6, 7] and [8, 10] all start at or before 8, so absorb them, giving [3, 10]. Add it, then copy [12, 16].
Result: [[1, 2], [3, 10], [12, 16]].
List [[1, 3], [6, 9]], new interval [2, 5]. What is the result?
- A[[1, 5], [6, 9]]
- B[[1, 9]]
- C[[1, 3], [2, 5], [6, 9]]
Show the answer
[[1, 5], [6, 9]]. [1, 3] overlaps [2, 5] and widens it to [1, 5]. 6 > 5, so [6, 9] is copied unchanged.
Insert into a sorted list
intervals is sorted by start and no two of its intervals overlap (both ends are included in every interval). Add the interval added, merging it with every interval it overlaps, and return the list, still sorted and without overlaps.
intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], added = [4, 8] → [[1, 2], [3, 10], [12, 16]]
0 ≤ intervals.length ≤ 10,000 · 0 ≤ start ≤ end ≤ 1,000,000,000 · intervals is sorted and has no overlaps