题目
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
解题
方法一：排序+贪心
写法一：按照第一个数排序
按照第一个数字进行排序
如果满足条件，那么res++,更新pre
如果不满足条件，那么pre要取第二个数最小的，这样更好满足后面的pair （贪心）
class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { int res=1; sort(pairs.begin(),pairs.end(),[](vector<int>& a,vector<int>&b){ return a[0]<b[0]; }); int pre=pairs[0][1]; for(int i=1;i<pairs.size();i++){ if(pairs[i][0]>pre){ res++; pre=pairs[i][1]; }else{ pre=min(pre,pairs[i][1]);//贪心:选第二个数比较小的 } } return res; } };
写法二：按照第二个数进行排序
class Solution { public: int findLongestChain(vector<vector<int>>& pairs) { int res=1; sort(pairs.begin(),pairs.end(),[](vector<int>& a,vector<int>&b){ return a[1]<b[1]; }); int pre=pairs[0][1]; for(int i=1;i<pairs.size();i++){ if(pairs[i][0]>pre){ res++; pre=pairs[i][1]; } } return res; } };
