Insert Interval Approach

Process in three phases:

$1.$ Add all intervals that end before the new interval starts

$2.$ Merge all intervals that overlap with the new interval

$3.$ Add all intervals that start after the new interval ends

function insertInterval(intervals, newInterval)
    result := []
    i := 0

    // Phase 1: intervals ending before new starts
    while i < n and intervals[i].high < newInterval.low
        result.add(intervals[i])
        i := i + 1

    // Phase 2: merge overlapping
    while i < n and intervals[i].low <= newInterval.high
        newInterval.low := min(newInterval.low, intervals[i].low)
        newInterval.high := max(newInterval.high, intervals[i].high)
        i := i + 1
    result.add(newInterval)

    // Phase 3: intervals starting after new ends
    while i < n
        result.add(intervals[i])
        i := i + 1

    return result