Insert Interval
Medium
Intervals
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.
TimeO(n)SpaceO(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).