56. Merge Intervals

MediumIntervals and Sweep LineSorting + linear scanSort by start, then sweep-and-merge

Merge Intervals

Given an array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Open official problem prompt ↗

In plain English

Take a pile of possibly-overlapping ranges and produce the smallest set of disjoint ranges that covers exactly the same points.

Picture it like this

Think of highlighting overlapping stretches on a calendar: any two marks that touch or overlap become one continuous highlighted block.

Example

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Why: [1,3] and [2,6] overlap (3 >= 2) so they combine into [1,6]; the other two touch nothing.

Constraints

1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^4

Pattern lesson

See the pattern, then code

Sort by start, then sweep-and-merge

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Once intervals are sorted by start, any interval that overlaps the current group must start before the group's running end; so only the most recent merged interval can ever absorb the next one.

New words, made simpleKnow these before the algorithm

Interval: A pair [start, end] representing a continuous range of values.
Overlap: Two intervals overlap when one starts at or before the other ends.
Merge: Replace overlapping intervals with a single interval spanning their union.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Pairwise comparison

Quadratic and needlessly complex; the sort-based method dominates it.

Repeatedly scan for any two intervals that overlap and fuse them until no overlaps remain.

Time O(n^2)Space O(n)

Best choiceSort then sweep-merge

Sorting guarantees overlaps are adjacent, so a single pass finishes the job.

Sort by start; keep a running result and extend the last interval whenever the next one overlaps it.

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

The rule we keep true

Invariant

The merged list always holds disjoint intervals sorted by start, and its last interval's end is the largest end seen so far among intervals processed in the current group.

Why this is correct

Reasoning

Because intervals are sorted by start, any interval that overlaps an earlier one must overlap the most recent merged interval; if the current start exceeds that end, no later interval can reach back either, so a new group safely begins.

The algorithm in three movesSay these aloud before coding

1Sort intervals by start value

merged = [[1,3]]

2Walk through them keeping a running merged list

start 2 <= end 3 -> extend to [1,6]

3If the current start is <= the last merged interval's end, extend that end

merged = [[1,6],[8,10],[15,18]]

4Otherwise append the current interval as a new group

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,3]0

[2,6]1

[8,10]2

[15,18]3

1 · Read[[1,3],[2,6],[8,10],[15,18]]

2 · AskWhat order guarantees adjacency of overlaps?

3 · Update statealready sorted by start

4 · Resultorder unchanged

Key takeaway

After sorting, [1,3] and [2,6] overlap and collapse into [1,6].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Sort by start
Guarantees that intervals belonging to the same merged block appear consecutively.
2
Lines 5-9Sweep and merge
Extend the last interval when the current one overlaps, otherwise start a fresh interval.
3
Lines 6Overlap test uses <=
Using <= treats touching intervals like [1,3] and [3,5] as overlapping, matching the union semantics.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single interval returns unchanged
Intervals fully contained in another (e.g. [1,5] then [2,3])
Intervals that merely touch at endpoints (e.g. [1,4] and [4,5])
Already-sorted vs shuffled input

Common beginner mistakes

Forgetting to sort, which breaks the adjacency assumption
Overwriting the end with the new end instead of max(end, current) when the current interval is nested
Using < instead of <= and failing to merge touching intervals

Check your understanding

Why is it safe to only compare against the last interval in the merged list rather than all of them?

Merge Intervals

Merge Intervals

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line