力扣上一道抽到英文原题现场还没写出来的easy难度的mid题-526互联

646. Maximum Length of Pair Chain

很难绷，今天去华东理工面试抽到了这个英文原题，虽然我也没写过，但是区间操作的题目大多都需要排序预处理，想到了排序预处理，也想到了第二个判断应该怎么写，第一个判断当时脑子一片空白，然后就一直卡在那，最后连最基本的思路都没说就进入了下一个环节。。。（血亏）

思路：

1.首先进行排序预处理

2.我们考虑用x，y分别表示已选择组成区间链的最后一个区间，也就是[a,b]->[c,d]->...->[x,y]\ (满足题目条件的已确定的区间链)

3.紧接着我们遍历pairs数组，对于当前i结点的pairs[i]，如果能通过当前pairs[i]将y缩小我们就对[x,y]进行更新；

4.如果不能将y缩小我们就考虑能否将当前pairs[i]加入到[x,y]后面，更新ans，同时更新x,y的值指向区间链最后一个区间；

5.如果不能加入到区间链的后面我们直接跳过该区间pairs[i]

Code c++

 1     class Solution
 2     {
 3     public:
 4         int findLongestChain(vector<vector<int>> &pairs)
 5         {
 6             sort(pairs.begin(), pairs.end());
 7             int x = pairs[0][0], y = pairs[0][1], ans = 1, n = pairs.size();
 8             for (int i = 1; i < n; i++)
 9             {
10                 if (pairs[i][1] < y)
11                     x = pairs[i][0], y = pairs[i][1];
12                 else if (pairs[i][0] > y)
13                 {
14                     x = pairs[i][0], y = pairs[i][1];
15                     ans++;
16                 }
17             }
18             return ans;
19         }
20     };