Given a list of pairs, build the longest chain where each next pair starts after the previous pair ends.
You are given an array of integer pairs. A pair ([a, b]) can be followed by another pair ([c, d]) if and only if (b < c). A valid chain is a sequence of pairs where every pair after the first can be placed after the previous one using this rule.
Return the maximum possible length of such a chain.
The goal is to choose pairs so that the chain is as long as possible, not necessarily to use all pairs.
Input Format
- An array of integer pairs
pairs, where each pair has two integers[start, end]. - Each pair represents an interval-like segment with
start < end.
Output Format
- Return a single integer: the length of the longest valid pair chain.
Constraints
- 1 <=
pairs.length - Each pair contains exactly 2 integers.
- For every pair
[a, b], assumea < b. - Pairs may be unsorted and may overlap.
Example 1
Input
pairs = [[1,2],[2,3],[3,4]]
Output
2
Explanation
A valid longest chain is [[1,2], [3,4]]. The pair [2,3] cannot follow [1,2] because 2 is not less than 2.
Example 2
Input
pairs = [[1,2],[7,8],[4,5]]
Output
3
Explanation
All three pairs can be chained as [[1,2], [4,5], [7,8]].
Show 1 more example
Example 3
Input
pairs = [[1,10],[2,3],[4,5],[6,7]]
Output
3
Explanation
One longest chain is [[2,3], [4,5], [6,7]].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.