力扣题解（ 最长数对链）

646. 最长数对链

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

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

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

思路：

规定dp[i]是以i位置元素为最后一个元素的最大长度，此时dp[i]与dp[i-1]之间的关系无法确定，因为pair数组此时是无序的，以i位置元素为最后一个的最大长度可能包含下标大于i的元素，因此需要先对pairs数组重新排列，保证以i位置为最后一个元素时，所有可能包含的元素全在（0-i-1）中。为保证这个特性，规定一个比较函数，然后对pairs重新排雷，比较的方法可以是比较pair所有的right元素，或者比较left元素，然后按照从小到大排列。之所以按照left，right都行的原因是，若按照left排，则（0-i-1）的所有的right元素有小于或大于i位置处left元素，而（i+1-n）位置元素的right位置元素一定大于i位置left元素。而以right比较时，（i+1，n）位置的元素的right大于i位置left，故以left或right作比较元素均可以满足要求。

class Solution {
public:static bool cmp(const vector<int>&p1,const vector<int>&p2) {return p2[0]>p1[0];}int findLongestChain(vector<vector<int>>& pairs) {int n=pairs.size();sort(pairs.begin(),pairs.end(),cmp);vector<int>dp(n,1);vector<int>maxx(n);maxx[0]=pairs[0][1];dp[0]=1;for(int i=1;i<n;i++){  int a=pairs[i][0];int b=pairs[i][1];for(int j=0;j<i;j++){if(a>maxx[j]){//有构成新的最长的可能if(dp[i]<dp[j]+1){dp[i]=dp[j]+1;}}maxx[i]=b;}}int ret=dp[0];for(auto e:dp){ret=max(ret,e);}return ret;}
};