Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given an array of intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the input ranges.
Constraints & assumptions
- 1 ≤ intervals.length ≤ 10⁴
- intervals[i].length == 2
- 0 ≤ startᵢ ≤ endᵢ ≤ 10⁴
In plain English
Think of busy blocks on a calendar. Overlapping meetings are hard to reason about when they're jumbled, so first you line them all up by start time. Now order works in your favour: any meeting can only overlap with the one you're currently holding onto.
You sweep left to right holding the latest merged block. If the next meeting starts after your block ends, there's a gap — you start a new block. Otherwise they overlap, so you simply stretch the current block's end to cover both. One clean pass and every overlap has quietly folded together.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1Sort the intervals by their start value.
- 2Walk through them, keeping a list of merged results.
- 3If the current interval starts after the last merged one ends, append it as a new block.
- 4Otherwise they overlap — extend the last block's end to max(lastEnd, currentEnd).
The solution
Sort + Sweep
Sort by start, then merge each interval into the previous one.
Sorting guarantees overlaps are adjacent, so a single left-to-right pass can fold each interval into the last kept one. This is the canonical, optimal approach.
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
int n = merged.size();
if (n == 0 || merged.get(n - 1)[1] < interval[0]) {
merged.add(interval);
} else {
merged.get(n - 1)[1] = Math.max(merged.get(n - 1)[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}