Insert Interval

Given sorted, non-overlapping intervals and a new interval, insert it so the list stays sorted and non-overlapping, merging where needed.

A way to picture it

You're sliding a new booking into a tidy calendar. Everything that ends before it stays put. Everything it touches gets swallowed, and the booking stretches to cover them. Everything that starts after it just shuffles along.

How to approach it

One pass in three phases: copy intervals that end before it, merge the ones that overlap, copy the ones that start after.

Example

Input: {"intervals":[[1,3],[6,9]],"newInterval":[2,5]}. Output: [[1,5],[6,9]].

Complexity: O(n) time and O(n) space. Each interval is looked at once; the output holds up to n + 1 intervals.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.