Difficulty: MediumIntervals

Merge Intervals

Problem in Plain English

You are given an unsorted list of intervals and must combine every group of overlapping ones. Return the merged non-overlapping intervals covering exactly the same points.

Problem Statement

Given an array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals.

Two intervals overlap when they share at least one point, so touching intervals like [1,4] and [4,5] merge into [1,5]. Return the non-overlapping intervals covering exactly the same ranges as the input.

Constraints

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

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Intervals [1,3] and [2,6] overlap and merge into [1,6]; the other two touch nothing.

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

The intervals touch at 4, which counts as overlapping, so they merge into [1,5].

Example 3

Input: intervals = [[5,5]]
Output: [[5,5]]

A zero-length closed interval still covers point 5. One interval needs no merge and is returned as an independently owned row.

Example 4

Input: intervals = [[8,10],[1,3],[2,9]]
Output: [[1,10]]

The last interval [2,9] bridges the earlier disjoint blocks [1,3] and [8,10]. Absorbing just one block would leave overlapping output and fail to represent the fully merged result.

Example 5

Input: intervals = [[1,10],[2,3],[10,10]]
Output: [[1,10]]

The nested interval contributes no new endpoints, and the point interval at 10 touches the outer interval. Taking the maximum end prevents the nested interval from shrinking the covered range.

Intuition

Each merged block represents a connected covered range, so combining two overlapping intervals takes the smaller start and larger end. Touching endpoints count as overlap here. Example 1 combines [1,3] with [2,6] to form [1,6]. A new interval can bridge several existing blocks, so the unsorted approach must inspect every block; start-time sorting makes only the most recent merged block relevant.

Approaches

Pairwise Merge

Solution Details

Reveal Pairwise Merge: intuition, complexity, and code

Intuition

Maintain disjoint blocks without sorting the input. For each new interval, combine it with every overlapping existing block and keep all disjoint blocks. The maintained disjointness makes one pass over the blocks sufficient, even when the new interval bridges several of them. Sort the final blocks to give a consistent ascending output.

Step-by-Step Logic

Copy the first input row into an owned output block; never reuse input rows as mutable output. Example 1 starts with [1,3].
For each remaining input interval, create an owned current range and an empty kept list. Inspect every existing block using the inclusive test current start <= block end and block start <= current end.
On overlap, widen current to the minimum start and maximum end; otherwise retain the existing block. Example 1 absorbs [1,3] into current [2,6], obtaining [1,6].
After all blocks are checked, append current to kept and replace the block list. Example 1 keeps [1,6] when reading [8,10], then keeps both blocks when reading [15,18].
Sort the final blocks by start before returning. Example 1 returns [[1,6],[8,10],[15,18]]. A bridge interval may absorb multiple blocks, so do not stop at the first overlap.

Why It Works

Inductively, the existing blocks are pairwise disjoint and their union equals the processed input union. Replacing an overlapping block and the current interval by their bounding interval preserves their union because they share a point. Nonoverlapping blocks are retained. A block skipped earlier cannot become overlapping after a later absorption: it is disjoint from both the original current range and that later block, and the union of two overlapping ranges has no gap to cross the skipped block. Thus one pass absorbs all connected blocks and leaves pairwise disjoint output covering exactly the new union. Final sorting changes only output order.

Dry Run

Pairwise Merge: variable states at each step
Input index	Current before	Existing block	Inclusive overlap	Current / kept after	Block list after interval
0	[1,3]	-	seed copied row	current [1,3]	[[1,3]]
1	[2,6]	[1,3]	2 <= 3 and 1 <= 6	current [1,6]; kept []	[[1,6]]
2	[8,10]	[1,6]	8 <= 6 false	current [8,10]; kept [[1,6]]	[[1,6],[8,10]]
3	[15,18]	[1,6]	15 <= 6 false	current [15,18]; kept [[1,6]]	pending next block
3	[15,18]	[8,10]	15 <= 10 false	current [15,18]; kept [[1,6],[8,10]]	[[1,6],[8,10],[15,18]]
return	-	-	final start sort	no order change	[[1,6],[8,10],[15,18]]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the input count and k the final block count. When no intervals overlap, each new interval scans all earlier blocks and constructs a replacement reference list, giving O(n^2) comparisons and O(n^2) reference slots allocated cumulatively. Only O(n) list slots and owned two-value rows are live at once, so peak additional space is O(n). Final O(k log k) sorting is dominated by O(n^2), with up to O(k) sorting workspace. Output holds O(k) rows; Java also allocates a final k-reference array. Input rows and order remain unchanged; Python uses index loops to avoid a sliced input tail.

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3
4class Solution {5    public int[][] merge(int[][] intervals) {6        List<int[]> res = new ArrayList<>();7        res.add(new int[]{intervals[0][0], intervals[0][1]});8        for (int i = 1; i < intervals.length; i++) {9            int[] cur = new int[]{intervals[i][0], intervals[i][1]};10            List<int[]> kept = new ArrayList<>();11            for (int[] block : res) {12                // Touching counts as overlap; inspect all blocks because cur can bridge several.13                if (cur[0] <= block[1] && block[0] <= cur[1]) {14                    cur[0] = Math.min(cur[0], block[0]);15                    cur[1] = Math.max(cur[1], block[1]);16                } else {17                    kept.add(block);18                }19            }20            kept.add(cur);21            res = kept;22        }23        res.sort((x, y) -> Integer.compare(x[0], y[0]));24        return res.toArray(new int[res.size()][]);25    }26}

Hints

Hint 1

Overlapping intervals are only guaranteed to sit together after sorting.

Hint 2

Once sorted by start, each interval can only overlap the most recently merged block.

Hint 3

Extend that block end to the larger of the two ends, or append a fresh block when the new start clears it.

Edge Cases

A single interval returns unchanged with no merging needed.
Touching intervals [1,4] and [4,5] merge into [1,5].
A fully nested interval like [2,3] inside [1,10] disappears into the outer bounds.
Equal-start intervals merge into the longest end; duplicate rows contribute no new points.
A zero-length interval [5,5] is legal and merges with any closed interval containing point 5.
An unsorted bridge such as [2,9] after [8,10] and [1,3] must absorb both blocks.

Common Mistakes and Interview Tips

An unsorted approach must compare against every maintained block. Merely comparing the last block misses distant overlaps and bridge intervals.
Setting the merged end to the current interval end instead of the maximum, which shrinks blocks that fully contain the newcomer.
Using a strict overlap comparison fails to merge touching closed endpoints; this differs from Meeting Rooms.
Sorting the caller container or extending an input row accidentally mutates the supplied intervals; copy the outer container and allocate owned result rows.
Stopping pairwise merging after one absorbed block misses a newcomer that bridges several blocks.
Interview tip: state the disjoint-block invariant and explain why only the final block can extend after sorting.

Key Takeaway

Sorting by start lets finalized blocks stay closed: compare each incoming interval only with the final merged block, extending its maximum end or appending an owned new block.