Maximum Length of Pair Chain
You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.
A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length longest chain which can be formed.
You do not need to use every pair in the given input. You can select pairs in any order.
Examples
Input: [[1,2],[2,3],[3,4]]
Output: 2
Input: [[1,2],[7,8],[4,5]]
Output: 3
Hints
After sorting the pairs by their ending value, initialize the chain with the first pair and keep track of the last selected pair's end value.
Iterate through the sorted pairs, and for each pair, if its start value is greater than the last selected pair's end value, include it in the chain and update the last selected pair's end value.
To maximize the chain length, consider using dynamic programming where `dp[i]` represents the length of the longest chain ending with the `i-th` pair, and compute it by checking all previous pairs that can form a valid chain with the current pair.
Related Problems
Maximum Length of Pair Chain
You are given an array of `n` pairs `pairs` where `pairs[i] = [lefti, righti]` and `lefti < righti`.