646. Maximum Length of Pair Chain思路解析

题目

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: 2 Explanation: The longest chain is [1,2] -> [3,4] Note: The number of given pairs will be in the range [1, 1000].

思路解析

要想尽量多地拼接pair，那么就应该在每次迭代的当前sub chain中末尾的pair的第二个元素值尽可能小，所以先对 Input中的pairs 按照 第二元素 升序排列，然后再遍历一次挨个判断能否连接成链条，最后链条的pair数量就是最终结果

Python实现

class Solution(object): def findLongestChain(self, pairs): """ :type pairs: List[List[int]] :rtype: int :Runtime: 112 ms """ pairs.sort(key=operator.itemgetter(1,0)) max = -float("inf") sum = 0 for i in pairs: if i[0] > max: sum += 1 max = i[1] return sum

C++实现

// Runtime: 76 ms class Solution { private: static bool compare(vector<int> a, vector<int> b) { if (a[1] == b[1]) return a[0] < b[0]; return a[1] < b[1]; }; public: int findLongestChain(vector<vector<int>>& pairs) { std::sort(pairs.begin(), pairs.end(), compare); int max = INT_MIN, sum = 0; for (int i = 0; i < pairs.size(); ++i) { if (pairs[i][0] > max) { sum += 1; max = pairs[i][1]; } } return sum; } };

时间复杂度

不管是直接使用语言内置的sort函数还是自己实现的排序函数，都是nlogn，没有最坏情况的时间复杂度小于nlogn的算法。