Merge Intervals — Interval List Intersections
↗ LeetCode: Interval List Intersections · Medium · pattern chapter →
Asked atMetaGoogleAmazon
Two lists of sorted, disjoint intervals. Return their intersection.
Example 1 — A=[[0,2],[5,10],[13,23],[24,25]], B=[[1,5],[8,12],[15,24],[25,26]] → [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]Example 2 — A=[], B=[[1,2]] → []
Constraints — 0 ≤ A.length, B.length ≤ 1000. Brute pairs every A×B — O(m·n) = 10⁶ ops at m=n=10³. Two-pointer sweep (advance the interval ending first) is O(m+n) = 2·10³ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — All pairs
O(n·m). Baseline.
Approach 2 — Two-pointer merge (canonical)
Insight. Both lists sorted → at each step, compute intersection of A[i] and B[j]; advance whichever ends first.
Intersection = [max(starts), min(ends)] if nonempty.
java
int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> out = new ArrayList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi) out.add(new int[]{lo, hi});
if (A[i][1] < B[j][1]) i++; else j++;
}
return out.toArray(new int[0][]);
}Execution Trace
Step 1 / 3A ends first → i++
Complexity — Time O(n + m); Space O(1) extra.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| All pairs | O(n·m) | O(1) | baseline |
| Two-pointer | O(n+m) | O(1) | optimum |
When to use which
- Two sorted disjoint lists → two-pointer.
- k lists intersection → generalize with k pointers; complexity O(N·k).
- "Union of intervals" → merge intervals template instead.
AI Study CompanionBeta
Related problems
- Merge Intervals
- Employee Free Time — k-list union
- [Interval Union / Difference] — variants
Was this page helpful?
📚 Related problems