DSA problem
Maximum Length of Pair Chain
You are given an array of n pairs pairs where pairs[i] = [left_i, right_i] and left_i < right_i. A pair p2 = [c, d] can follow another pair p1 = [a, b] if and only if b < c. A chain of pairs can be formed in this fashion. Return the length of the longest chain that can be formed. You do not need to use up all the given pairs; you can select pairs in any order.
Because we may reorder the pairs, this is structurally identical to the classic "interval scheduling" / "max non-overlapping intervals" problem. Once we sort the pairs by their right endpoint ascending, a clean greedy works: scan left to right, always extending the chain with the next pair whose left endpoint is strictly greater than the last selected pair's right endpoint. Greedy by earliest-end-time is optimal because finishing earliest leaves the most room for future pairs.
A natural DP-based alternative also works: sort by the first coordinate, then run an LIS-style DP dp[i] = max over j < i of dp[j] + 1 whenever pairs[j][1] < pairs[i][0]. That gives O(n^2) time and is a useful contrast because it generalizes when constraints are richer than "non-overlap".
The optimal approach is the sort-and-greedy variant, which runs in O(n log n) time (dominated by the sort) and O(1) extra space beyond the sort. We track current_end, the right endpoint of the most recently chosen pair, and count, the chain length. Each new pair either extends the chain (if its left endpoint exceeds current_end) or is discarded.
Examples
pairs = [[1,2],[2,3],[3,4]]2pairs = [[1,2],[7,8],[4,5]]3pairs = [[-10,-8],[8,9],[-5,0],[6,10],[-6,-4],[1,7],[9,10],[-4,7]]4Constraints
- n == pairs.length
- 1 <= n <= 1000
- -1000 <= left_i < right_i <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.