# 646.最长数对链

## 问题描述
[646. 最长数对链 (Medium)](https://leetcode.cn/problems/maximum-length-of-pair-chain/)

给你一个由 `n` 个数对组成的数对数组 `pairs` ，其中 `pairs[i] = [leftᵢ,
rightᵢ]` 且 `leftᵢ < rightᵢ`
现在，我们定义一种 **跟随** 关系，当且仅当 `b < c` 时，数对 `p2 = [c, d]` 才可以跟在
`p1 = [a, b]` 后面。我们用这种形式来构造 **数对链** 。
找出并返回能够形成的 **最长数对链的长度** 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
**示例 1：**
```
输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。
```
**示例 2：**
```
输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
```
**提示：**
- `n == pairs.length`
- `1 <= n <= 1000`
- `-1000 <= leftᵢ < rightᵢ <= 1000`

## 解题思路
### 贪心
在选择第一个数对时，必定选择使`pairs[i][1]`最小的那个`i`，第二个数对则必定选择`pairs[j][0] > pairs[i][1]`且使`pairs[j][0]`最小的`j`，因此类推，因此我们将`pairs`按照其第二个元素升序排列。

### 动态规划

## 代码
### 贪心
```cpp
class Solution {
  public:
    int findLongestChain(vector<vector<int>> &pairs) {
        auto cmp = [&](vector<int> &v1, vector<int> &v2) {
            if (v1[1] == v2[1]) {
                return v1[0] <= v2[0];
            }
            return v1[1] < v2[1];
        };
        std::sort(pairs.begin(), pairs.end(), cmp);
        int cnt = 1;
        int left = pairs[0][1];
        for (int i = 1; i < pairs.size(); i++) {
            if (pairs[i][0] > left) {
                cnt++;
                left = pairs[i][1];
            }
        }
        return cnt;
    }
};
```