链接: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;
}
};