GreedyAlgorithmaka interval merging, union of intervals, sweep line

Merge Intervals

Sort intervals by start and sweep once, extending the current interval while the next one overlaps and emitting it when a gap appears.

Pattern: Greedy Practice (4)

Progress

Overview

Given a list of [start, end] intervals, return the minimal list of disjoint intervals covering the same points. After sorting by start, overlapping intervals are adjacent, so a single pass suffices: keep a current interval; if the next interval starts at or before current.end, extend current.end = max(current.end, next.end); otherwise emit current and begin a new one.

The pattern generalizes to almost every interval question — insert an interval, intersect two lists, count rooms, find free time — by changing what happens at overlap and at gap. The sort is what makes greedy correct; on unsorted input a later interval can bridge two earlier ones.

greedyintervalssortingsweep lineone pass

Intuition

A mental model before the formal terms.

Lay the intervals as strips of tape on a number line, then walk left to right. As long as the next strip starts before the tape you are currently holding ends, it just makes that tape longer. The first time you see daylight between the tape and the next strip, you tear off the tape and start a new one.

How it works

Sort intervals by start (ties by end are irrelevant).
Initialize current = intervals[0].
For each subsequent [s, e]: if s ≤ current.end, set current.end = max(current.end, e). Else push current to the output and set current = [s, e].
Push the final current. Use s < current.end instead of ≤ if touching intervals must stay separate.

Why it works

Invariant: after processing the first k sorted intervals, the output plus current is exactly the union of those k intervals as disjoint pieces, with current being the piece with the largest start.

Greedy-choice / exchange. Because intervals are sorted by start, the next interval starts at or after current.start. If it overlaps current, its union with current is a single interval, so merging is forced — no optimal output could keep them apart. If it does not overlap, it starts after current.end and, since all later intervals start even later, nothing can ever extend current again; emitting it is safe. Either way the choice is the only one consistent with any correct output.

The output is minimal because consecutive emitted intervals are separated by a genuine gap that no input interval covers.

Recognition

How to tell a problem wants this.

"Merge overlapping intervals", "union of ranges", "total covered length", "insert a new interval into a sorted list".
Any question where sorting by start and scanning with a running end is the natural model: free time between meetings, employee schedules, interval intersections.
Input up to 10^5 intervals — O(n log n) sort-and-sweep is the target.

“maximum number of non-overlapping” → Greedy “overlapping intervals” → Intervals

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1sort intervals by start
2out = []; cur = intervals[0]
3for [s, e] in intervals[1:]:
4  if s <= cur.end: cur.end = max(cur.end, e)
5  else: out.push(cur); cur = [s, e]
6out.push(cur)
7return out

Implementations

1# Merge intervals: sort by start, then sweep once extending the current
2# interval while the next one overlaps, emitting when a gap appears.
3# CONVENTION: closed real intervals [start, end]. Touching merges ([1,3] and
4# [3,6] become [1,6]) but merely adjacent does not ([1,3] and [4,6] stay
5# separate). gaps() and covered_length() use the same convention, so a gap is
6# the open span between two covered ranges and a length is end - start.
7 
8 
91 · Sort by start; the sweep depends entirely on that ordering
10def merge(iv: list[tuple[int, int]]) -> list[tuple[int, int]]:
11    if not iv:
12        return []
13    ordered = sorted(iv)  # tuples compare lexicographically: start, then end
14 
15    out: list[list[int]] = [list(ordered[0])]
16    for s, e in ordered[1:]:
172 · Overlap (or touch) means extend the current end; otherwise emit
18        if s <= out[-1][1]:
19            out[-1][1] = max(out[-1][1], e)
20        else:
21            out.append([s, e])
22    return [(s, e) for s, e in out]
23 
24 
253 · Inserting one interval into an already-merged list is a three-phase scan
26def insert(sorted_iv: list[tuple[int, int]], add: tuple[int, int]) -> list[tuple[int, int]]:
27    out: list[tuple[int, int]] = []
28    lo, hi = add
29    i = 0
30    n = len(sorted_iv)
31    # everything strictly before the new interval
32    while i < n and sorted_iv[i][1] < lo:
33        out.append(sorted_iv[i])
34        i += 1
35    # everything overlapping it, absorbed into (lo, hi)
36    while i < n and sorted_iv[i][0] <= hi:
37        lo = min(lo, sorted_iv[i][0])
38        hi = max(hi, sorted_iv[i][1])
39        i += 1
40    out.append((lo, hi))
41    # everything strictly after
42    out.extend(sorted_iv[i:])
43    return out
44 
45 
464 · The complement: the uncovered gaps within [lo, hi], same convention
47def gaps(merged: list[tuple[int, int]], lo: int, hi: int) -> list[tuple[int, int]]:
48    out: list[tuple[int, int]] = []
49    cursor = lo
50    for s, e in merged:
51        if s > cursor:
52            out.append((cursor, s))
53        cursor = max(cursor, e)
54    if cursor < hi:
55        out.append((cursor, hi))
56    return out
57 
58 
595 · Total covered length, which merging makes a trivial sum
60def covered_length(merged: list[tuple[int, int]]) -> int:
61    return sum(e - s for s, e in merged)

Walkthrough

sorted(iv) needs no key: tuples compare lexicographically, so (start, end) order comes for free — the one language here where the default is exactly right.
The working list holds *lists* rather than tuples because the sweep mutates out[-1][1]; the final comprehension converts back to tuples for an immutable result.
for s, e in ordered[1:] unpacks in the loop header, though the slice copies — itertools.islice(ordered, 1, None) avoids that for large inputs.
out.extend(sorted_iv[i:]) appends the entire tail in one call, which is faster than a loop.
sum(e - s + 1 for s, e in merged) is the covered length as a one-line generator.

Complexity (this implementation)

time O(n log n) for merge, O(n) for the rest · space O(n)

The ordered[1:] slice is an extra O(n) copy; islice removes it without changing the loop.

Language notes

Tuple lexicographic comparison makes sorted(iv) correct with no key, which is a genuine convenience over the other three languages.
Tuples are immutable, so the in-place extension needs lists — converting back at the end keeps the public type immutable.
list.extend(iterable) is a single C-level call and beats a Python loop of append.
ordered[1:] copies; itertools.islice(ordered, 1, None) is the lazy alternative.

Common mistakes in this language

Trying to mutate a tuple in the sweep (out[-1][1] = ... on a tuple), which raises TypeError.
Slicing in the loop header on a very large list and doubling memory.
Assuming sorted(iv) sorts only by start — it also orders by end, which here is harmless and occasionally relied upon.

Language differences that matter here

Sorting pairs by start-then-end is free in C++ (std::pair default ordering) and Python (tuple ordering), needs an explicit two-key comparator in JS/TS, and in JavaScript the default is actively wrong because it stringifies.
Mutability of the accumulator differs: C++ pair and JS/TS arrays are mutable in place, while Python tuples are not — so the Python version sweeps over lists and converts back.
TypeScript tuple spreading widens to number[], so output tuples must be built by explicit indexing — a friction the other three do not have.
Appending a tail: Python list.extend(slice) is one call, C++ needs insert with iterators, and JS/TS need a loop or a spread.

Complexity

Best

O(n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Sorting dominates; O(n) if already sorted by start (the Insert Interval variant). Output excluded, O(log n) for in-place sort.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Union, coverage length, or gaps of a set of intervals.
Insert Interval: input already sorted — skip the sort and do the linear sweep.
Pre-processing before other interval logic (e.g. checking if a query range is fully covered).

Avoid it when

Skipping the sort: [[1,4],[5,6],[2,5]] in input order gives [1,4] then [5,6] then [2,5] cannot merge back into the emitted [1,4], producing three intervals; sorted, the answer is one interval [1,6]. Greedy without the sort is wrong, not just slow.
Counting overlap depth (rooms needed) — merging loses the multiplicity; use Interval Scheduling with a heap or a +1/−1 sweep.
Dynamic inserts and deletes with queries in between — maintain an ordered set / balanced tree of disjoint intervals or a Segment Tree instead of re-merging each time.

Alternatives

Interval Scheduling Activity Selection Segment Tree Difference Array

Common mistakes

Extending with cur.end = e instead of max(cur.end, e) — a short interval inside a long one shrinks the merged result.
Comparing against the wrong element (the next input interval instead of the last output interval).
Wrong boundary convention (< vs ≤) for touching intervals.
Mutating the input intervals when the caller still needs them.

Interview patterns

Merge Intervals, Insert Interval, Interval List Intersections (two-pointer variant over two sorted lists).
Employee Free Time: merge all schedules, then output the gaps.
Meeting Rooms I: after sorting, any overlap between neighbours means one person cannot attend all.

Interview questions on this

Greedy or dynamic programming?Advanced
Convincing me your algorithm is correctExpert

Mock interviews

Merge IntervalsIntermediate

Example problems

Interval List Intersectionsmedium Meeting Rooms IImedium Merge Intervalsmedium Non-overlapping Intervalsmedium