Insert Interval

You are given an array of non-overlapping intervals sorted by start time. Your task is to insert a new interval into this list and merge any necessary intervals to maintain the sorted, non-overlapping property.

Example:

• Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
• Output: [[1,5],[6,9]]
• Why? [2,5] overlaps with [1,3]. Combining them gives [1,5].

Since the list is already sorted, we can solve this in O(N) time using a single pass with three phases:

1. Skip Left: Add all intervals that come strictly before the new interval (where end < newStart).
2. Merge Overlaps: Use a while loop to process intervals that overlap with the new one (where start <= newEnd). Continuously update the new interval to [min(start), max(end)].
3. Append Right: Once overlaps are resolved, add the (possibly expanded) new interval, then add all remaining intervals.

Visualize the three-phase linear scan strategy.