LeetCode 57 Insert Interval - Solution

Three phases in a single pass:

$1.$ Add all intervals that end before new interval starts (no overlap, completely before).

$2.$ Merge all intervals that overlap with new interval. Track the merged interval's min start and max end.

$3.$ Add all intervals that start after new interval ends (no overlap, completely after).

This exploits the sorted order to process in $O(n)$ time.