最长数对链的长度

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种 跟随 关系，当且仅当 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 <= lefti < righti <= 1000

 贪心算法：

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
    // 按照数对的右端点进行排序
    sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    
    int currentEnd = INT_MIN; // 当前链的最后一个数对的右端点
    int maxLen = 0; // 最长链的长度
    
    for (const auto& pair : pairs) {
        if (currentEnd < pair[0] ) { // 如果当前数对的左端点大于链的最后一个数对的右端点
            currentEnd = pair[1];   // 更新链的右端点
            maxLen++;            // 链长度+1
        }
    }
    
    return maxLen;
}
};

     sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

return a[1] < b[1]：这一行是排序的核心逻辑。它比较 a 和 b 的第二个元素（即数对的右端点）。如果 a 的右端点小于 b 的右端点，返回 true，则 a 在排序中会排在 b 前面。这意味着按右端点的升序排序。

贪心算法通常通过选择局部最优解来达到全局最优解,在这如果选择左端点的排序可能会导致后续选择的数对受限，从而无法形成最长链。如果我们选择了右端点较大的数对，可能会限制接下来可以选择的数对。例如，如果选择了一个右端点为较大的数对，后面的一些数对就可能无法与其连接，从而导致未能形成更长的链。

由于lefti < righti ，排序时按照右端点（即数对的第二个元素）进行排序，可以确保我们首先选择那些结束较早的数对。这意味着我们可以更快地“释放”当前数对的右端点，从而有更多的空间选择后续的数对。

DP：

class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
    int n = pairs.size();
    
    // 按照左端点排序
    sort(pairs.begin(), pairs.end());
    
    // dp[i] 表示以第 i 个数对为结尾的最长链的长度
    vector<int> dp(n, 1); // 初始每个数对都可以独立构成一个长度为 1 的链
    
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (pairs[j][1] < pairs[i][0]) { // 如果 pairs[j] 可以接在 pairs[i] 前面
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return *max_element(dp.begin(), dp.end());
}

};

 创建一个 dp 数组，其中 dp[i] 表示以第 i 个数对为结尾的最长链的长度。初始化时，每个数对都可以独立构成一个长度为 1 的链，因此将 dp 数组初始化为 1。

检查条件 pairs[j][1] < pairs[i][0]：

即如果数对 pairs[j] 的右端点小于数对 pairs[i] 的左端点，说明可以将 pairs[j] 接在 pairs[i] 前面。更新 dp[i] 为 max(dp[i], dp[j] + 1)，dp[j] + 1表示选择 pairs[j] 加上 pairs[i] 的情况。