Free lesson · DSA Mastery - Interview Prep, End to End
Merge Intervals
Merge Intervals
Merge Intervals opens the Merge & Insert sub-group with the section's signature operation: given a collection of intervals, merge all overlapping ones into the minimal set of disjoint intervals. Sorting by start lets a single sweep keep a "current" merged interval, extending its end whenever the next interval overlaps and emitting it (starting fresh) when a gap appears. It is the full generalization of the Summary Ranges sweep to true spans with the overlap test, and the foundation that Insert Interval and Remove Covered Intervals build directly upon. We present the brute-force repeated-merge baseline and the sort + sweep (canonical).
The insight: after sorting by start, any interval that overlaps the current merged span must start at or before the current span's end - and because starts are non-decreasing, all intervals that belong to one merged block are contiguous in sorted order. So a single pass suffices: hold a current interval, and for each next interval either absorb it (extend the current end to the max of the two ends) or, if it starts beyond the current end, close out the current and open a new one. Sorting is what makes overlaps adjacent.
The Problem
Given an array of 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.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap → merge into [1,6]. The rest are disjoint.
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] are considered overlapping (touching) → [1,5].
Constraints:
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^4
Approaches Overview
| # | Approach | Time | Space | Verdict |
|---|---|---|---|---|
| 1 | Repeatedly scan & merge any overlapping pair | O(n²) | O(n) | Baseline |
| 2 | Sort by start + single sweep | O(n log n) | O(n) | Canonical |
The brute force repeatedly scans for any overlapping pair, merges it, and restarts until no overlaps remain - correct but quadratic. The canonical approach sorts by start, then sweeps once: a current interval absorbs each overlapping successor (extending its end) or is emitted when a gap appears. Because sorting makes the members of each merged block contiguous, one pass produces the minimal disjoint set. Here touching intervals ([1,4],[4,5]) are treated as overlapping.
Approach 1: Repeated Scan & Merge - Baseline
The Idea
While any two intervals overlap, find such a pair, replace them with their merged interval, and repeat. Each merge reduces the count by one, but locating a pair is O(n²) per round and there can be O(n) rounds - overall poor. Correct but illustrative only.
Complexity
Time: O(n²) or worse. Space: O(n).
Approach 2: Sort by Start + Single Sweep - Canonical
The Idea
Sort intervals by start. Initialize current to the first interval. For each subsequent interval iv: if iv.start <= current.end, it overlaps (or touches) - extend current.end = max(current.end, iv.end). Otherwise there's a gap - append current to the result and set current = iv. After the loop, append the final current. The result is the minimal set of disjoint intervals.
Logic Flowchart
graph TD
A["sort intervals by start"] --> B["current = intervals[0]"]
B --> C["for iv in intervals[1..]"]
C --> D{"iv.start <= current.end?"}
D -->|Yes overlap| E["current.end = max(current.end, iv.end)"]
D -->|No gap| F["append current; current = iv"]
E --> C
F --> C
C --> G["append current; return result"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows the merge sweep. After sorting by start, a current interval absorbs each overlapping successor by extending its end, or is appended and replaced when a gap appears, with the final current appended at the end.
Code
public static int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // by start
List<int[]> result = new ArrayList<>();
int[] current = intervals[0].clone();
for (int i = 1; i < intervals.length; i++) {
int[] iv = intervals[i];
if (iv[0] <= current[1]) { // overlap or touch
current[1] = Math.max(current[1], iv[1]); // extend the merged end
} else { // gap: close current, open new
result.add(current);
current = iv.clone();
}
}
result.add(current); // final interval
return result.toArray(new int[result.size()][]);
}
// Usage:
// merge([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]
This Java code sorts intervals by start, then sweeps with a current interval, extending its end on overlap or appending it and starting fresh on a gap, finally appending the last current interval.
Step-by-Step Walkthrough
A frame-by-frame trace on intervals = [[1,3],[2,6],[8,10],[15,18]]:
graph LR
F0["sorted; current=[1,3]"]
F1["[2,6]: 2<=3 overlap → current=[1,6]"]
F2["[8,10]: 8>6 gap → emit [1,6]; current=[8,10]"]
F3["[15,18]: 15>10 gap → emit [8,10]; current=[15,18]; emit → [[1,6],[8,10],[15,18]]"]
F0 --> F1 --> F2 --> F3
style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
This walkthrough merges the intervals. One-three absorbs two-six into one-six; then eight-ten and fifteen-eighteen are disjoint, giving one-six, eight-ten, fifteen-eighteen.
Result: [[1,6],[8,10],[15,18]].
Complexity
Time: O(n log n) - sort dominates; the sweep is O(n). Space: O(n) for the result.
Complexity Comparison
| Approach | Time | Space | Key Idea | When to Use |
|---|---|---|---|---|
| Repeated scan & merge | O(n²) | O(n) | Merge any overlapping pair, repeat | Tiny inputs |
| Sort by start + sweep | O(n log n) | O(n) | Overlapping members are contiguous after sorting | Canonical |
Sorting transforms the problem: members of each merged block become contiguous, so a single sweep with a current interval produces the minimal disjoint set. This is the full sweep-and-emit pattern from Summary Ranges, now with the overlap test and end-extension - the template Insert Interval and Remove Covered Intervals reuse.
Variations & Follow-ups
Why does sorting by start guarantee that all members of a merged block are contiguous?
Consider any set of intervals that should merge into one block - they form a connected chain of overlaps. After sorting by start, take the earliest-starting member; every other member of the block starts at or before that member's reach (directly or transitively through the chain), and crucially, no interval from a different block can start between two members of this block, because that would require it to start after this block's earliest start but before the block's coverage ends - which would make it overlap the block and thus belong to it. So in start order, each merged block occupies a contiguous run. That's what lets a single left-to-right sweep, holding one current interval, capture an entire block before emitting it. Without sorting, block members could be scattered, forcing the quadratic repeated-merge.
Why extend the current end with max(current.end, iv.end) rather than just iv.end?
When iv overlaps current, the merged interval must cover both, so its end is the larger of the two ends. It's tempting to assume iv.end >= current.end (since iv starts later), but that's false: iv can be entirely contained within current - e.g., current = [1, 10], iv = [2, 5]. Here iv.start <= current.end (overlap) but iv.end = 5 < current.end = 10, so taking iv.end would wrongly shrink the merged interval. Using max keeps the coverage correct in both the extend case and the contained case. This is a classic, easy-to-miss bug: sorting orders by start, not end, so a later-starting interval can still finish earlier.
Why does iv.start <= current.end (with <=) correctly handle touching intervals?
This problem treats touching intervals as overlapping (Example 2 merges [1,4] and [4,5] into [1,5]), modeling closed intervals where the shared endpoint counts. The condition iv.start <= current.end uses <=, so iv.start == current.end (4 <= 4) triggers a merge - exactly the desired behavior. If a problem instead treated intervals as half-open (touching does not merge, as in the meeting-room family), you'd use strict <. The single character difference between < and <= encodes the endpoint convention, and choosing it correctly per the problem statement is essential. Always confirm whether touching should merge before writing the comparison.
How do Insert Interval and Remove Covered Intervals build on this sweep?
Insert Interval is Merge Intervals applied to an already-sorted, already-disjoint list plus one new interval: you can skip the sort (the list is sorted) and sweep once, copying intervals before the new one, merging the overlapping middle stretch into the new interval, then copying the rest - an O(n) specialization. Remove Covered Intervals uses the same sort (by start, then by end descending as a tiebreak) and a sweep that tracks the largest end seen; an interval is "covered" when its end doesn't exceed that running max. Both reuse the core insight - sort so related intervals are adjacent, sweep with a running summary (current interval or max end). Merge Intervals is the canonical parent of the sub-group.
What about edge cases?
- Single interval: No merging; return it as-is.
- All intervals overlap into one (e.g., a chain): The sweep extends
currentrepeatedly, emitting one interval. - Fully disjoint input: Every interval is emitted unchanged (each triggers a gap).
- Contained interval (
[1,10]then[2,5]): Themaxkeeps the end at 10; contained intervals don't shrink the block. - Touching (Example 2): Merged because
<=is used.
Common Interview Pitfalls
- Setting
current.end = iv.endinstead ofmax(...). Breaks on contained intervals. - Forgetting to emit the final
current. The last block is appended only after the loop. - Wrong endpoint comparison. Use
<=if touching should merge,<if not. - Mutating the input array. Clone intervals before modifying ends to avoid corrupting the source.
Why This Topic Matters
Merge Intervals is the signature interval operation and the full realization of the sort-by-start sweep: hold a current span, extend on overlap (via max of ends), emit on gap. It cements why sorting makes merge-block members contiguous and the contained-interval max subtlety - the exact template that Insert Interval and Remove Covered Intervals specialize.
The next topic, Insert Interval, specializes the merge to a common real-world case: given a list of non-overlapping, sorted intervals and a single new interval, insert it and merge any resulting overlaps. Because the existing list is already sorted and disjoint, no full sort is needed - a single linear pass copies intervals entirely before the new one, merges the stretch that overlaps the new interval into it, and copies the rest. It is Merge Intervals optimized for the "one insertion into a clean list" scenario, achieving O(n) by exploiting the pre-existing order.