Maximum Length of Pair Chain
Medium · Greedy · Array · Dynamic Programming · Greedy · Sorting
Problem
You are given n pairs pairs[i] = [left_i, right_i] with left_i < right_i. A pair [c, d] can follow a pair [a, b] in a chain when b < c (strictly).
You may choose any subset of the pairs and arrange them in any order. Return the length of the longest chain you can build.
Examples
Input: pairs = [[1,2],[7,8],[4,5]] Output: 3
[1,2] → [4,5] → [7,8].
Input: pairs = [[1,5],[2,3],[4,6],[5,9]] Output: 2
For example [2,3] → [4,6]. No three pairs can chain: [2,3] → [4,6] needs a pair starting after 6, and none does.
Input: pairs = [[1,2],[2,3]] Output: 1
2 < 2 is false, so the pairs cannot link.
Constraints
- 1 <= n <= 1000
- -1000 <= left_i < right_i <= 1000
Approaches
- Baseline: longest chain ending at each pair — time O(n²), space O(n)
Follow-up
What if the pairs must stay in their given order, or you need how many longest chains exist? The greedy no longer answers either: see the use cases “Longest chain without reordering” and “How many longest chains”.
Related problems
Start free on Cariara · Coding problems · System design studio
