Merge Intervals Pattern

CodingMid2 min read · 6 problemsUpdated Nov 11, 2026

Sort intervals by start, then sweep merging overlaps.

When to Use It

Overlapping ranges, meeting rooms, calendar conflicts, interval insertion.

Classic example: Merge overlapping meeting intervals.

How It Works

Sorting intervals by start coordinate turns overlap detection into a linear sweep: once sorted, the only interval that can overlap the current 'open' interval is the next one. You either extend the open interval's end (overlap) or close it and start a new one (no overlap). Total cost is O(n log n) from the sort, O(n) for the sweep.

The overlap test itself is subtle: 'overlap' usually means current.start <= open.end, but 'touching' intervals like [1,2] and [2,3] may or may not count as overlapping depending on the problem (closed vs half-open intervals). Read the problem twice.

Variations decide what to do at the merge step. Merging unions the endpoints; counting meeting rooms uses a sweep-line with start/end events instead; interval insertion can skip the sort and do a three-phase walk (before, overlap, after). The pattern's general framing: sort by one coordinate, sweep maintaining state, is the precursor to sweep-line algorithms in computational geometry.

Key Insight

Sorting by start coordinate guarantees that any future interval overlapping the current open interval must arrive next, reducing all-pairs overlap detection from O(n^2) to a single O(n) sweep after the O(n log n) sort.

Sort by start, then sweep: overlap → extend the current; gap → start a new one.

Templates

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] iv : intervals) {
    if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < iv[0]) {
        merged.add(iv);
    } else {
        merged.get(merged.size() - 1)[1] =
            Math.max(merged.get(merged.size() - 1)[1], iv[1]);
    }
}
return merged.toArray(new int[0][]);

intervals.sort(key=lambda x: x[0])
merged = []
for iv in intervals:
    if not merged or merged[-1][1] < iv[0]:
        merged.append(iv)
    else:
        merged[-1][1] = max(merged[-1][1], iv[1])
return merged

Common Pitfalls

Sorting by end instead of start (or vice versa) and getting greedy-scheduling vs merging confused.
Using < instead of <= in the overlap test, missing touching intervals when they should merge.
Mutating the input array's intervals in place when the problem expects a new list.
For insert-interval, forgetting that the new interval may merge with multiple existing intervals (loop, don't single-step).
For meeting-rooms-II, trying to merge intervals instead of using a min-heap of end times or a start/end event sweep.

Variations

Merge all overlapping intervals: sort by start, sweep with one open interval.
Insert interval into sorted non-overlapping list: three-phase walk, no resort needed.
Meeting rooms II / minimum rooms: min-heap of end times, or sweep-line with +1/-1 events.
Interval intersection of two sorted lists: two pointers, advance whichever ends first.
Offline interval queries: Minimum Interval to Include Each Query sorts intervals and queries, then sweeps with a min-heap keyed by interval size.

Big O

Time: O(n log n)
Space: O(n)

Sorting intervals by start time dominates at n log n; the merge sweep itself is linear. Space is O(n) for the output list of merged intervals (O(1) extra if merging in place).

Next PatternCyclic Sort