Greedy — Maximum Length of Pair Chain
↗ LeetCode: Maximum Length of Pair Chain · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Pair [a,b] chains with next [c,d] iff c > b. Return longest chain length.
Example 1 — pairs=[[1,2],[2,3],[3,4]] → 2Example 2 — pairs=[[1,2],[7,8],[4,5]] → 3
Constraints — 1 ≤ n ≤ 1000. Brute enumerates 2ⁿ chains — 10³⁰ ops at n=10². Sort by second-of-pair + linear pass (activity selection) is O(n log n) = ~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 — DP (LIS-style)
Sort by first; O(n²) DP.
Approach 2 — Sort by second + greedy (canonical)
Insight. Activity selection: sort by second value; greedily pick every pair whose start > last picked end.
java
int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
int end = Integer.MIN_VALUE, count = 0;
for (int[] p : pairs) if (p[0] > end) { end = p[1]; count++; }
return count;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n log n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DP | O(n²) | O(n) | baseline |
| Sort + greedy | O(n log n) | O(1) | canonical |
When to use which
- Chain length → sort by end + greedy.
- "Return the chain" → track predecessor indices.
- "Weighted chain" → DP required.
AI Study CompanionBeta
Related problems
Was this page helpful?