Merging intervals

Problem

Interval questions hand you pairs [start, end]: meetings, bookings, ranges of numbers, spans of a string. They ask you to combine the ones that overlap, to add one more range to a tidy list, or to decide whether any two collide. Compared pair by pair, n intervals give about n²/2 comparisons, and the merged result can still depend on chains (A overlaps B, B overlaps C, but A and C are far apart). Sorting by start removes both problems: after the sort, only neighbours in the scan ever need comparing.

Intuition

Picture the intervals as bars on a timeline. Slide a finger from left to right and keep track of one thing: the block of overlapping bars you are currently inside, and where it ends. When the next bar starts before that end, it belongs to the same block, and the block may stretch further right. When it starts after the end, there is a gap, the block is finished for good, and a new one begins.

Why can a finished block never grow again? Every later bar starts at or after the bar that just opened the new block, and that start is already past the finished block's end. Sorting by start guarantees this, which is the whole trick.

Rows are in sorted order. A row can only touch the block opened above it; once a gap appears, earlier blocks are final. The diagram scrolls sideways on a narrow screen.

Mechanics

Merge: the invariant

Sort by start. Keep a list merged of disjoint blocks. The invariant after processing the first k intervals is: merged is exactly the union of those k intervals, written as disjoint blocks in increasing order, and every block except possibly the last is final, meaning no unprocessed interval can touch it.

For the next interval [s, e], compare s with the last block's end. If s ≤ end the two overlap (or touch), so set end = max(end, e); the max matters because a short interval can sit entirely inside a long one. Otherwise open a new block. In the second case the old last block becomes final: every remaining interval starts at s or later, and s is already past its end. That proves the invariant carries forward, and at the end it says merged is the answer.

Closed or half-open?

Read the problem for whether [1, 4] and [4, 5] overlap. For ranges of numbers they share the point 4, so they merge (use ≤). For meetings, one ending at 10 and the next starting at 10 do not clash, because a meeting is the half-open range [start, end) (use <). That one character is the most common bug in this family.

Insert into a sorted, disjoint list

When the existing list is already sorted and disjoint, do not append and re-sort. Walk it once in three phases:

1. Copy every interval that ends before the new one starts. They cannot touch it.
2. While the next interval starts at or before the new one's end, absorb it: the new interval becomes [min(starts), max(ends)].
3. Append the grown interval, then copy everything left. Those start after it ends.

The absorbed intervals form one contiguous run, because the list is sorted by start and disjoint, so their ends are sorted too. That is why a single pass suffices.

The amber run is contiguous in the sorted list, so one forward pass finds it.

Detecting any overlap

To answer "does anything overlap?", sort by start and compare each interval only with the one before it. Why is that enough? Suppose no neighbouring pair overlaps, so each interval ends no later than the next one starts. Chaining those inequalities, interval i ends no later than any later interval j starts, so no pair at all overlaps. Turned around: if any two intervals overlap, some neighbouring pair in start order does too.

Worked example

Merge. The intervals [5, 8], [1, 4], [2, 3], [9, 12], [12, 14], [6, 7], [16, 17] sort by start to [1, 4], [2, 3], [5, 8], [6, 7], [9, 12], [12, 14], [16, 17]. Then the scan goes:

The answer is [1, 4], [5, 8], [9, 14], [16, 17]. Note that [12, 14] extends [9, 12] because closed intervals that share an endpoint overlap.

Insert. Adding [5, 11] to [1, 2], [4, 6], [7, 8], [10, 13], [15, 16]: phase 1 copies [1, 2], phase 2 absorbs [4, 6], [7, 8], [10, 13] and grows the new interval to [4, 13], and phase 3 copies [15, 16]. The result is [1, 2], [4, 13], [15, 16].

Meetings. Sorted, the meetings [9, 10), [10, 12), [11, 13), [13, 15) first clash at [10, 12) and [11, 13). Drop the clashing one and the remaining [9, 10), [10, 12), [13, 15) can all be attended: back-to-back meetings that share an endpoint are fine.

Implementation

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Variations and edge cases

def insert(intervals, new):
    start, end = new
    result, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < start:
        result.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    result.extend(intervals[i:])
    return result


def can_attend_all(meetings):
    meetings = sorted(meetings)
    return all(prev[1] <= cur[0] for prev, cur in zip(meetings, meetings[1:]))


def intersect(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        lo, hi = max(a[i][0], b[j][0]), min(a[i][1], b[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if a[i][1] < b[j][1]:   # the one that ends first cannot meet anything later
            i += 1
        else:
            j += 1
    return out

• Forgetting max. Writing merged[-1][1] = end shrinks a block when a short interval sits inside a long one, as [2, 3] does inside [1, 4] above.
• Touching endpoints. Decide ≤ or < from the problem's meaning, not by habit.
• Mutating the input. merged.append([start, end]) builds a fresh list; appending the input's own list and then editing it changes the caller's data.
• Empty input. All three functions return an empty result or True without special cases; check yours does too.
• Insert at the ends. The new interval may go before everything, after everything, or absorb everything. Each phase loop may run zero times.

Complexity and tradeoffs

• Merge: O(n log n) for the sort, O(n) for the scan, O(n) output space.
• Insert: O(n) time, because the list is already sorted. Binary search finds where phase 2 begins in O(log n), but copying the output is still O(n).
• Any overlap: O(n log n) for the sort, O(1) extra space if you sort in place.
• Baseline. Checking every pair is O(n²), and merging by repeated pairwise unions can take O(n²) passes in the worst case.
• When it is the wrong tool. Merging answers "what is covered?", not "how many at once?" or "which to drop?". Counting simultaneous intervals needs a sweep line or a heap of end times; choosing a maximum set of disjoint intervals needs the greedy rule that sorts by end. When intervals arrive one at a time and queries interleave, a balanced tree or a sorted container keyed by start keeps each insert at O(log n).

Problems

Start with Meeting Rooms to practise sorting and comparing neighbours, then Merge Intervals for the full invariant, then Insert Interval to do it without a sort. Each one is a different question asked of the same sorted scan.

Easy

• 252. Meeting Rooms Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Sort the meetings by start time; someone is double-booked only if a meeting starts before the previous one ends.

Medium

• 56. Merge Intervals Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Sort by start, then each interval either overlaps the last merged one and extends it or begins a new block.
• 57. Insert Interval Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Copy intervals that end before the new one, absorb every interval that overlaps it, then copy the rest.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 435. Non-overlapping Intervals Medium
• 759. Employee Free Time Hard
• 1235. Maximum Profit in Job Scheduling Hard
• 1851. Minimum Interval to Include Each Query Hard

Connections

Sorting before scanning is the move from the Python toolkit page: sorted on tuples orders by start and then by end for free. Removing the fewest intervals to make the rest disjoint is a greedy problem that sorts by end instead, and the intersection variant above is two pointers walking two sorted lists. Counting how many intervals overlap at once moves from a single open block to a heap of end times.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, section 16.1 on activity selection and section 14.3 on interval trees.
• Skiena, S., The Algorithm Design Manual, section 4.1 on applications of sorting, including interval problems.
• Sedgewick and Wayne, Algorithms, section 2.5 on applications of sorting.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.