原題鏈接
題目原文：
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對數(shù)字。每對數(shù)字中佳簸，第一個數(shù)字總是小于第二個數(shù)字辜昵。
現(xiàn)在宽堆，我們假定數(shù)字對的鏈的定義——一對數(shù)字（c,d）,可以排在數(shù)字對（a, b）后面，當且僅當b < c.
給定一套數(shù)字對摔敛，求鏈的最長長度柜与。你不需要使用所有的數(shù)字對愕把。你可以隨意安排數(shù)字對的順序。
例子1:
輸入[[1,2], [2,3], [3,4]] 輸出2
解釋：最長鏈是[1,2] -> [3,4]
其實這是側(cè)面考察的貪心算法问词，并且要求能夠有效排序數(shù)組督函。這個題目類似于安排開會的起止時間，之前l(fā)eetcode有很多題目激挪。
那么辰狡，排序就需要按照每個數(shù)字對的第二個數(shù)字升序排列，因為結(jié)束時間早的垄分，那肯定開始時間也更早宛篇。
思路：每當我們找到新的節(jié)點，則加到鏈中薄湿，并把這個節(jié)點作為尾節(jié)點叫倍，然后繼續(xù)尋找。
int findLongestChain(vector>& pairs) {?
????if (pairs.empty()) return 0; ?// 判斷輸入是否為空
? ? // 自定義排序方法豺瘤，按照第二個數(shù)字來升序
????auto mySort = [](vector& A, vector& B){ return A[1] < B[1];};
????sort(pairs.begin(), pairs.end(), mySort); // 排序
????int pos = 0,res = 1; // pos為當前尾節(jié)點的位置，初始尾節(jié)點是第一個元素，res為長度
????for (int i = 1; i < pairs.size(); i++) {
? ? // 按順序?qū)ふ医匦停绻业轿补?jié)點陶冷，就更新
? ? ????if (pairs[i][0] > pairs[pos][1]) {
? ? ? ? ? ? ? ? res += 1;
? ? ? ? ? ? ? ? pos = i;
? ? ? ? ?????}
? ? ? }
? ? ? ? return res；
}
