Medium

题目描述

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对 (c, d) 才可以跟在 (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

解题思路

这道题可以用两种方法解决：动态规划和贪心算法。

方法一：贪心算法（推荐） 贪心策略是按照每个数对的右端点进行排序，然后依次选择不冲突的数对。这种方法基于一个重要观察：为了让链尽可能长，我们应该尽可能早地"释放"位置，即优先选择右端点较小的数对。

具体步骤：

  1. 按照数对的右端点升序排序
  2. 遍历排序后的数对，维护当前链的最后一个数对的右端点
  3. 如果当前数对的左端点大于链末尾的右端点，则可以加入链中

方法二：动态规划 定义 dp[i] 为以第 i 个数对结尾的最长链长度。对于每个数对，检查之前所有能够连接的数对，取最大值加1。

时间复杂度上，贪心算法为 O(n log n)，动态规划为 O(n²)，所以贪心算法更优。

代码实现

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 count = 1;
        int end = pairs[0][1];
        
        for (int i = 1; i < pairs.size(); i++) {
            if (pairs[i][0] > end) {
                count++;
                end = pairs[i][1];
            }
        }
        
        return count;
    }
};

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        
        count = 1
        end = pairs[0][1]
        
        for i in range(1, len(pairs)):
            if pairs[i][0] > end:
                count += 1
                end = pairs[i][1]
        
        return count

public class Solution {
    public int FindLongestChain(int[][] pairs) {
        Array.Sort(pairs, (a, b) => a[1].CompareTo(b[1]));
        
        int count = 1;
        int end = pairs[0][1];
        
        for (int i = 1; i < pairs.Length; i++) {
            if (pairs[i][0] > end) {
                count++;
                end = pairs[i][1];
            }
        }
        
        return count;
    }
}

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[1] - b[1]);
    
    let count = 1;
    let end = pairs[0][1];
    
    for (let i = 1; i < pairs.length; i++) {
        if (pairs[i][0] > end) {
            count++;
            end = pairs[i][1];
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度贪心算法动态规划
时间复杂度O(n log n)O(n²)
空间复杂度O(1)O(n)

其中 n 为数对的数量。贪心算法的时间复杂度主要来自排序，空间复杂度为常数级别；动态规划需要额外的 dp 数组存储状态。

相关题目