Pattern 2: Insert into a sorted set

What if the list is already sorted and non-overlapping, and you need to fit in a new interval? Taking advantage of the fact that it's already organized lets you solve it in one pass, without re-sorting — by dividing the list into three phases.

🎯

Try it first: Insert Interval

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given a list of intervals that is sorted and non-overlapping and a new interval, insert it (merging if necessary) keeping the list sorted and non-overlapping.

Example: intervals = [[1,3],[6,9]], new = [2,5] → [[1,5],[6,9]].

Carregando editor…

Tried it? You could add the new one, re-sort, and merge everything (the previous lesson) — but that throws away the information that the list was already sorted. The theory below does it in O(n), without sorting.

The theory: three phases on the line

Since the list is already sorted and non-overlapping, the intervals split naturally into three groups relative to the new interval:

1. BEFORE:    end before the new one starts   (end < new.start)
              → copy them unchanged
2. OVERLAP:   touch the new one               (start <= new.end)
              → merge them all into the new one (min of starts, max of ends)
3. AFTER:     start after the new one ends
              → copy them unchanged

You scan the list once, going through these three phases in order. Phase 2 is the heart: while the current interval touches the new one, it gets absorbed — new = [min(starts), max(ends)]. At the end of phase 2, the new (now merged) one enters the result, and phase 3 just copies the rest.

See the three phases — note new (a scalar) growing as it absorbs the phase-2 intervals:

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

Why is it O(n) time (no sort!)?

The list already comes sorted, so we don't pay the O(n log n) of merge: a single linear pass classifies each interval into one of the three phases → O(n) time, O(n) space for the output. That's the advantage of exploiting the given structure (sorted) instead of re-sorting from scratch.

The lesson

When the problem statement guarantees that the input already has an order, don't waste it. Here, "already sorted" turns a merge problem (O(n log n)) into a three-phase linear one (O(n)). Always ask: what does the input already give me for free?

🧠 Review quiz

0/4

1. Why can you insert in O(n) (without sorting), while the general merge is O(n log n)?

2. What are the three phases of the insertion?

3. In the overlap phase, how is the new interval updated?

4. What is the transferable lesson of this class?

Summary

Insert into a sorted, non-overlapping list: three phases — before, merge, after — in one pass.
O(n) time (no sort!), because the input already comes sorted.
Lesson: exploit the given structure instead of reorganizing from scratch.

Next lesson: choosing what to keep with greedy reasoning.

All lessons in this section