Merge Intervals
Problem
[start, end] in arbitrary order.
Combine every group of intervals that overlap (touching endpoints count, e.g.
[1,4] and [4,5]) and return the resulting non-overlapping
intervals that cover exactly the same points.[[1,3],[2,6],[8,10],[15,18]]Output[[1,6],[8,10],[15,18]][[1,4],[4,5]]Output[[1,5]]1 ≤ n ≤ 104 · 0 ≤ start ≤ end ≤ 104
Try it yourself
class Solution {
public int[][] merge(int[][] intervals) {
}
}
Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.
Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.
Open the Intervals & Line Sweep guide →Approaches
Brute ForceRepeated Pairwise Merging
O(n³)Space O(n)Search all pairs for two overlapping intervals (a.start ≤ b.end
and b.start ≤ a.end), replace them by their union, and restart. Each
merge removes one interval and a full pair search costs O(n²); when no pair
overlaps, we are done.
public int[][] merge(int[][] intervals) { List<int[]> list = new ArrayList<>(); for (int[] in : intervals) list.add(in.clone()); boolean merged = true; while (merged) { merged = false; search: for (int i = 0; i < list.size(); i++) { for (int j = i + 1; j < list.size(); j++) { int[] a = list.get(i), b = list.get(j); if (a[0] <= b[1] && b[0] <= a[1]) { a[0] = Math.min(a[0], b[0]); a[1] = Math.max(a[1], b[1]); list.remove(j); merged = true; break search; } } } } return list.toArray(new int[0][]); }
Obviously correct, but cubic — hopeless for 104 intervals.
BetterInsert One by One into a Disjoint Set
O(n²)Space O(n)Maintain a result list that is always pairwise disjoint. For each new interval, absorb (and remove) every result interval it overlaps, then add the enlarged interval. It cannot overlap anything left, so the invariant holds.
public int[][] merge(int[][] intervals) { List<int[]> result = new ArrayList<>(); for (int[] in : intervals) { int[] cur = in.clone(); Iterator<int[]> it = result.iterator(); while (it.hasNext()) { int[] r = it.next(); if (r[0] <= cur[1] && cur[0] <= r[1]) { // overlap: absorb r cur[0] = Math.min(cur[0], r[0]); cur[1] = Math.max(cur[1], r[1]); it.remove(); } } result.add(cur); } return result.toArray(new int[0][]); }
One O(n) scan per interval; no sorting, but still quadratic.
OptimalSort by Start + Single Sweep
O(n log n)Space O(n)Sort by start. Walk the intervals: if the current start is ≤ the last merged
end, extend that end with max; otherwise begin a new block. Starts only
grow, so a gap means no later interval can reach back.
public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); for (int[] in : intervals) { if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < in[0]) { merged.add(new int[] {in[0], in[1]}); // gap: new block } else { int[] last = merged.get(merged.size() - 1); last[1] = Math.max(last[1], in[1]); // overlap: extend } } return merged.toArray(new int[0][]); }
Dry runsorted [[1,3],[2,6],[8,10],[15,18]] → merged list
- [1,3]1-3Lempty → add
- [2,6]1-6L2 ≤ 3 → end=6
- [8,10]1-68-10L6 < 8 → new
- [15,18]1-68-1015-18L10 < 15 → new ✔
Sorting dominates; the merge itself is a single linear pass.
Integer.compare (not a[0] - b[0]) in comparators
to stay overflow-safe for any value range.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Repeated Pairwise Merging | O(n³) | O(n) |
| Better | Insert One by One into a Disjoint Set | O(n²) | O(n) |
| Optimal | Sort by Start + Single Sweep | O(n log n) | O(n) |
- Overwriting the end with
in[1]instead ofmax— breaks on nested intervals like [1,10],[2,3]. - Using
<vs≤wrongly — touching intervals [1,4],[4,5] must merge. - Forgetting to sort first — the sweep only works on start-ordered input.
- Clarify whether touching endpoints count as overlap.
- Draw intervals on a number line — makes the sorted sweep obvious.
- Mention that sorting in place mutates the caller's input; copy if that matters.