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.