问题描述 链接到标题

646. 最长数对链 (Medium)

给你一个由 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按照其第二个元素升序排列。

动态规划 链接到标题

代码 链接到标题

贪心 链接到标题 

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;
    }
};