Merge Intervals
↗ LeetCode: Merge Intervals · Medium · pattern chapter →
Given a list of intervals, merge all overlapping ones and return the result.
Example 1 — [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]Example 2 — [[1,4],[4,5]] → [[1,5]] (touching = merging by convention)
Constraints — 1 ≤ n ≤ 10⁴. Brute checks every pair for overlap in O(n²) = 10⁸ ops at n=10⁴. Sort by start (O(n log n)) then linear sweep with a single "current" interval is O(n log n) = ~10⁵ ops = <10 ms.
Interview timer00:00
Approach 1 — Brute force (compare every pair)
Intuition. For each pair, if they overlap, merge and restart.
int[][] mergeBrute(int[][] intervals) {
List<int[]> list = new ArrayList<>();
for (int[] i : intervals) list.add(i);
boolean changed = true;
while (changed) {
changed = false;
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[1] >= b[0] && b[1] >= a[0]) {
list.set(i, new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])});
list.remove(j);
changed = true;
break;
}
}
}
return list.toArray(new int[0][]);
}Complexity — Time O(n³); Space O(n). Ugly.
Approach 2 — Sort + one-pass sweep
Insight from brute. Sort by start. Then overlap is a local decision: does the current interval start ≤ last-merged end? If yes, extend the end. If no, start a new bucket.
int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> out = new ArrayList<>();
int[] last = intervals[0];
out.add(last);
for (int i = 1; i < intervals.length; i++) {
int[] cur = intervals[i];
if (cur[0] <= last[1]) last[1] = Math.max(last[1], cur[1]);
else { last = cur; out.add(last); }
}
return out.toArray(new int[0][]);
}Complexity — Time O(n log n) (sorting dominates); Space O(n) for output. Optimal.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Pairwise merge until stable | O(n³) | O(n) |
| Sort + sweep | O(n log n) | O(n) |
When to use which
- Cold interview → jump straight to sort+sweep (brute is only worth stating).
- Touching vs strict overlap — clarify with the interviewer.
cur[0] <= last[1]merges touching;cur[0] < last[1]keeps them separate.
Related problems (same ladder applies)
- Insert Interval — insert one, then merge locally
- Interval List Intersections — two-pointer over two sorted interval lists
- Meeting Rooms — sorted + adjacent check
- Non-overlapping Intervals — greedy on end times