Insert Interval
The list is already sorted, so sweep it in three phases: before, overlapping, after.
Approach
Copy every interval that ends before the new one starts. Then, while intervals overlap it, absorb them by widening the new interval to the min start and max end, and push that merged interval once. Finally copy the remainder untouched. Because the input is sorted, this is a single linear pass with no sort of your own.
Time complexity
O(n)
Space complexity
O(n) for the output
Common mistake
Appending the new interval and re-running a full merge — correct, but it discards the sorted input and pays an unnecessary O(n log n).
See it run, step by step
Generate an interactive lesson for Insert Interval — trace every variable and watch the algorithm execute until it clicks.
Create a lesson with this problem