hardGreedyPure DSA~30 min
Longest Chain of Non-Overlapping Pairs
Given pairs [a, b] with a < b, a pair [c, d] can follow [a, b] only if b < c. Find the length of the longest chain you can form.
Problem
Given an array pairs where pairs[i] = [left, right] and left < right, a pair p2 can follow p1 if p1.right < p2.left. Return the length of the longest chain that can be formed; pairs may be used in any order.
Input
A list pairs of [left, right] with left < right.
Output
An integer: the longest chain length.
Constraints
- 1 <= pairs.length <= 1000
- -1000 <= left < right <= 1000
- Each pair may be used at most once.
Examples
Example 1
Input
pairs = [[1,2],[2,3],[3,4]]
Output
2
[1,2] -> [3,4] is the longest chain.
Example 2
Input
pairs = [[1,2],[7,8],[4,5]]
Output
3
[1,2] -> [4,5] -> [7,8] chains all three.