Insert Interval

Problem

You are given intervals, a list of closed integer intervals that is already sorted by start and contains no overlaps, plus one additional interval new_interval = [start, end]. Insert the new interval into the list and merge as necessary so the result is again sorted and non-overlapping. Two intervals that share an endpoint ([1,3] and [3,5]) are considered overlapping.

Return the resulting list. Do not simply append and re-sort; the interviewer expects you to exploit the existing order.

• Up to around ten thousand existing intervals.
• Endpoints are non-negative and fit comfortably in a normal int, for every interval including the new one.
• intervals is sorted by start and non-overlapping.

Examples

• intervals = [[2,4],[7,10]], new_interval = [3,6] → [[2,6],[7,10]]. The new interval overlaps only [2,4].
• intervals = [[0,1],[2,4],[5,6],[7,9],[10,14]], new_interval = [3,7] → [[0,1],[2,9],[10,14]]. [3,7] bridges [2,4], [5,6], and [7,9] into one block.
• intervals = [], new_interval = [5,7] → [[5,7]]. Inserting into an empty list.

Hints

1. Because the list is sorted and non-overlapping, the intervals that overlap the new one form a contiguous run. Where does that run start and end?
2. Split the list into three parts: strictly before the new interval, overlapping it, strictly after it. Only the middle part needs work.
3. Linear scan in three phases; the merged middle is [min(starts), max(ends)] over the new interval and every interval it touches.