• 0 ≤ intervals.length ≤ 10⁴
• Each interval and the new interval have the form [start, end] with start ≤ end
• The existing intervals are already sorted by start and are pairwise non-overlapping
• Intervals touching at an endpoint count as overlapping and are merged

The crucial words in the statement are "sorted" and "non-overlapping". The existing intervals already have the exact structure that Merge Intervals worked hard to build. Only one new interval disturbs the order, and it can only interfere with a contiguous run of the existing intervals — the ones its time range touches. Everything before that run is untouched, and everything after it is untouched.

That structure means you do not need to sort anything. You can walk the list once and stitch the new interval into place.

The tempting shortcut: append the new interval and run the full Merge Intervals routine.

def insert_naive(intervals, new):
    return merge(intervals + [new])     # sorts from scratch: O(N log N)

It works, but it throws away the sortedness you were handed and pays O(N log N) to rebuild an order that was already there. When a problem hands you a sorted input, re-sorting is almost always a sign you have missed the intended O(N) solution.

Because the list is sorted, the intervals fall into exactly three consecutive groups relative to the new interval, and you handle each group in one linear pass:

The key realisation is that the overlapping middle group is contiguous: once you pass an interval that starts after the new one's (possibly grown) end, no later interval can reach back, because the list is sorted by start. So a single forward walk cleanly separates the three groups.

def insert(intervals, new):
    res = []
    i, n = 0, len(intervals)

    # Phase 1: intervals ending before new starts — untouched.
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i])
        i += 1

    # Phase 2: intervals overlapping new — absorb them into new.
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    res.append(new)

    # Phase 3: intervals starting after new ends — untouched.
    while i < n:
        res.append(intervals[i])
        i += 1

    return res

One pass, O(N) time.

Answer [[1,5],[6,9]].

A case where the new interval swallows several: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8]. Phase 1 copies [1,2] and [3,5]? No — [3,5] ends at 5 which is not < 4, so only [1,2] is strictly before. Phase 2 absorbs [3,5], [6,7], [8,10] (all start ≤ the growing end) into [3,10]. Phase 3 copies [12,16]. Result [[1,2],[3,10],[12,16]] — one new interval devoured three existing ones.

The lesson here is about reading the shape of your input and refusing to discard it. A sorted, non-overlapping list is a strong precondition, and the intended solution almost always exploits it to reach O(N) rather than paying O(N log N) to recreate order that was already present.

The reusable structural insight — a single new element disturbs a sorted list only within a contiguous window, so a three-phase pass (before / affected / after) handles it in linear time — appears well beyond intervals: inserting into a sorted array, applying one update to a sorted event stream, splicing a range into a timeline. Whenever exactly one thing changes in an otherwise-ordered collection, look for the contiguous affected window and walk the three regions.

This is Merge Intervals with the sort already done for you and only one troublemaker to place. If you understood the anchor-and-sweep there, this is that same sweep, aimed at a single interval.