原题链接

题目原文：

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. 

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:

Input:[[1,2], [2,3], [3,4]]Output:2Explanation:The longest chain is [1,2] -> [3,4]

Note:

The number of given pairs will be in the range [1, 1000].

中文翻译：

给你n对数字。每对数字中，第一个数字总是小于第二个数字。

现在，我们假定数字对的链的定义——一对数字（c,d）,可以排在数字对（a, b）后面，当且仅当b < c.

给定一套数字对，求链的最长长度。你不需要使用所有的数字对。你可以随意安排数字对的顺序。

例子1:

输入[[1,2], [2,3], [3,4]] 输出2

解释：最长链是[1,2] -> [3,4]

其实这是侧面考察的贪心算法，并且要求能够有效排序数组。这个题目类似于安排开会的起止时间，之前leetcode有很多题目。

那么，排序就需要按照每个数字对的第二个数字升序排列，因为结束时间早的，那肯定开始时间也更早。

思路：每当我们找到新的节点，则加到链中，并把这个节点作为尾节点，然后继续寻找。

int findLongestChain(vector>& pairs) { 

    if (pairs.empty()) return 0;  // 判断输入是否为空

    // 自定义排序方法，按照第二个数字来升序

    auto mySort = [](vector& A, vector& B){ return A[1] < B[1];};

    sort(pairs.begin(), pairs.end(), mySort); // 排序

    int pos = 0,res = 1; // pos为当前尾节点的位置，初始尾节点是第一个元素，res为长度

    for (int i = 1; i < pairs.size(); i++) {

    // 按顺序寻找，如果找到尾节点，就更新

        if (pairs[i][0] > pairs[pos][1]) {

                res += 1;

                pos = i;

             }

      }

        return res；

}