链接
题目
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例
输入：[[1,2], [2,3], [3,4]] 输出：2 解释：最长的数对链是 [1,2] -> [3,4]
说明
给出数对的个数在 [1, 1000] 范围内。
思路一（贪心）
为了让数对链最长，让更多的数对加入到数对链当中，我们可以用贪心的思想。首先看以下一个例子：[[1,2], [3,4], [3,7],[5,6]]，我们可以发现，如果我们选择了[1,2],接下来选择[3,7]的话，那么这中间[3,7]之间的任何子序列都无法加入到数对链当中，相当于浪费了3个空间，而显然，如果我们选择了[1,2] [3,4] [5,6]，则能够充分利用这部分空间，因此我们采取以下贪心策略：
- 1. 根据每个数对的第2个数从小到大的顺序对原始数对数组进行排序。
- 2.遍历数对数组，只要遇到符合[i][0]>[i-1][1]的数对，就将其贪心的放入数对链当中，并更新数对链长度。
C++ Code
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 count=1;
int N2=pairs[0][1];
for(int i=1;i<pairs.size();i++)
{
if(pairs[i][0]>N2)
{
count++;
N2=pairs[i][1];
}
}
return count;
}
};