Insert interval: add a range to sorted intervals and merge overlaps

Given a list of non-overlapping closed intervals sorted by start, and a new interval, insert the new one and merge it with every interval it overlaps. Return the result, still sorted and without overlaps.

Interface

Unless you agree on a different interface with the interviewer, assume:

• insert_interval(intervals: list[list[int]], new: list[int]) -> list[list[int]]

Example

insert_interval([[1, 3], [6, 9]], [2, 5])                          ->  [[1, 5], [6, 9]]
insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) ->  [[1, 2], [3, 10], [12, 16]]
insert_interval([], [4, 8])                                        ->  [[4, 8]]
insert_interval([[1, 5]], [2, 3])                                  ->  [[1, 5]]      # contained
insert_interval([[3, 5]], [5, 7])                                  ->  [[3, 7]]      # closed: touching merges
insert_interval([[3, 5]], [0, 1])                                  ->  [[0, 1], [3, 5]]

Constraints

• Up to 10^5 intervals; start <= end in every interval.
• Intervals are closed, so [3, 5] and [5, 7] overlap.

Clarifying questions

• Closed or half-open intervals: do touching intervals merge?
• May I return a new list, or must I modify the input in place?
• Is the input guaranteed sorted and non-overlapping?

What a strong answer covers

• One pass in three phases: copy intervals that end before the new one starts; absorb every interval that starts no later than the new one ends, widening the new interval; append it, then copy the rest. O(n) time, O(n) output.
• Binary search to find the first and last overlapping intervals, which is O(log n) to locate but still O(n) to build the output.
• Edge cases: empty list, insertion at the beginning or end, the new interval containing several, or contained in one.

Follow-ups

• Insert many intervals one at a time and answer queries in between. Use a balanced tree keyed by start.
• Remove an interval from the set instead of inserting one.