Insert Interval

Problem

You are given intervals, a list of non-overlapping intervals sorted by start time, and a single newInterval. Insert newInterval into the list so that the list stays sorted and non-overlapping (merging where necessary), and return it.

Examples

Constraints

0 ≤ n ≤ 10⁴ · intervals is already sorted by start and already non-overlapping · newInterval may overlap zero, one, or many existing intervals.

Attempt it first

The lazy solution is one line: append newInterval to the list and run Module 14's Merge Intervals on the result. That is correct, and if you haven't solved it yet, do that first — it proves you understand the reduction. But then look hard at the two words in the problem statement you'd be throwing away: already sorted. Merge Intervals pays O(n log n) because it starts from arbitrary order. Here the order is a gift. Can you insert in a single linear pass and never sort at all?