一、题目
You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.
A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.
Example 1:
Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].
Example 2:
Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].
Constraints:文章来源：https://www.toymoban.com/news/detail-835990.html
n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti <= 1000文章来源地址https://www.toymoban.com/news/detail-835990.html
二、题解
class Solution {
public:
static bool cmp(vector<int>& a,vector<int>& b){
return a[0] < b[0];
}
int findLongestChain(vector<vector<int>>& pairs) {
int n = pairs.size(),len = 0;
sort(pairs.begin(),pairs.end(),cmp);
vector<int> ends(n,0);
for(int i = 0;i < n;i++){
int index = bs(ends,len,pairs[i][0]);
if(index == -1) ends[len++] = pairs[i][1];
else ends[index] = min(ends[index],pairs[i][1]);
}
return len;
}
int bs(vector<int>& ends,int len,int num){
int l = 0,r = len - 1,res = -1;
while(l <= r){
int mid = (l + r) / 2;
if(ends[mid] >= num){
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
return res;
}
};
到了这里，关于LeetCode646. Maximum Length of Pair Chain——动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
