Description
Given pairs where pairs[i] = [left, right], a pair p2 follows p1 if left2 > right1. Find the length of the longest chain.
Examples
Input:
pairs = [[1,2],[2,3],[3,4]]Output:
2Explanation:
[1,2]->[3,4].
Input:
pairs = [[5,10],[1,3],[8,12],[4,6],[15,20]]Output:
4Explanation:
The longest chain is [1,3]->[4,6]->[8,12]->[15,20]. Each pair's second element is less than the next pair's first element: 3 < 4, 6 < 8, and 12 < 15.
Input:
pairs = [[2,8],[6,7],[1,9]]Output:
1Explanation:
No pairs can be chained together because all pairs overlap. For example, [2,8] and [6,7] overlap since 6 < 8, so it is not possible to chain them (the requirement is 8 < 6). The maximum chain length is 1 using any single pair.
Constraints
- •
1 ≤ n ≤ 1000