646. Maximum Length of Pair Chain

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: 2Explanation: The longest chain is [1,2] -> [3,4]

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

思路： 使用Greedy来解决这个问题，那么只能是按照数组的第二个元素排序，(按照数组的第一个元素排序将会行不通）如 (8,9) (10,11) (1,100)。 按照数组第一个元素排序： (1,100)，(8,9)， (10,11) 。不能通过比较 [i] [end] 和 [i+1] [begin] 来增加链。 而如果按照数组第二个元素排序： (8,9) ，(10,11)， (1,100)，那么则可以通过比较 [i] [end] 和 [i+1] [begin] 来增加链。

class Solution public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, (a,b) -> a[1] - b[1]); int count = 0, end = Integer.MIN_VALUE; for (int[] pair : pairs) { if (pair[0] > end) { count++; end = pair[1]; } } return count; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。