[Leetcode]646.Maximum Length of Pair Chain

链接:LeetCode646

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

现在,我们定义一种跟随关系,当且仅当 b < c 时,数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合,找出能够形成的最长数对链的长度。你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: \([[1,2], [2,3], [3,4]]\)
输出: 2
解释: 最长的数对链是$ [1,2] -> [3,4]$

相关标签:动态规划

很明显这道题能通过动态规划解,令dp[i]表示为以索引i为结尾的最长数对链的长度,则当\(pairs[i][0] > pairs[j][1]\)时,\(dp[i] = max(dp[i],dp[j]+1)\),这样时间复杂度为\(O(N^2)\)。
另外一种比较巧妙的解法是,将pair按后一位进行排序以后,进行贪婪选取。为什么能这么做呢?考虑这样一个问题,假设我们的输入排完序后为\([[P_0,P_1],[P_2,P_3],[P_4,P_5],...]\),(也就是\(P_1<P_3<P_5<...\))那么要使得能够形成的最长数对链哪一个数对是一定会选的呢?
答案是\([P_0,P_1]\)数对,原因是:假设选了任意一个其他的数对组成的数对链,比如\([P_2,P_3],[P_4,P_5]\),因为\(P_1<P_3\),所以一定能够组成\([P_0,P_1],[P_4,P_5]\)数对链,并且如果满足\(P_1<P_2\),则能够组成\([P_0,P_1],[P_2,P_3],[P_4,P_5]\)数对链,也就是说选择以\([P_0,P_1]\)开始的数对链长度一定大于等于其他数对链长度,即要使得能够形成最长数对链\([P_0,P_1]\)数对是一定会选的。如此,贪婪选取即可,每次只需要记住上一次选取的数对中较大值即可。这样,时间复杂度为\(O(NlogN)\)。
两种方法如下所示:

python:

class Solution:
    # 动态规划
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort()
        n = len(pairs)
        dp = [1 for i in range(n)]
        for i in range(1,n):
            for j in range(i):
                if pairs[i][0] > pairs[j][1]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)
    # 贪婪
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort(key = lambda x:x[1])
        res = 1
        last = 0
        for i in range(n):
            if pairs[i][0] > pairs[last][1]:
                last = i
                res += 1
        return res

C++:

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {return a[1]<b[1];}
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end(),cmp);
        int res,last;
        res = 1;
        last = 0;
        for(int i = 0;i<pairs.size();i++){
            if(pairs[i][0] > pairs[last][1]){
                res ++;
                last = i;
            }
        }
        return res;
    }
};
上一篇:【WPF学习】第十二章 属性验证


下一篇:Leetcode 918. Maximum Sum Circular Subarray