水中的鱼: [Leetcode] Maximum Length of Pair Chain, Solution

水中的鱼: [Leetcode] Maximum Length of Pair Chain, Solution

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) . 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: 2 Explanation: The longest chain is [1,2] -> [3,4] Note: The number of given pairs will be in the range [1, 1000]. [Thoughts] [Code] 1: int findLongestChain(vector>& pairs) { 2: if(pairs.size() == 0) return 0; 3: 4: std::sort(pairs.begin(), pairs.end(), comp); 5: 6: int count = 1; 7: vector& pair = pairs[0]; 8: for(int i =1; i pair[1]) { 10: count ++; 11: pair = pairs[i]; 12: } 13: } 14: 15: return count; 16: } 17: 18: static bool comp(vector& a, vector& b) { 19:

Read full article from 水中的鱼: [Leetcode] Maximum Length of Pair Chain, Solution