给出 n 个数对。 在每一个数对中,第一个数字总是比第二个数字小。
现在,我们定义一种跟随关系,当且仅当 b < c 时,数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合,找出能够形成的最长数对链的长度。你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-length-of-pair-chain
这道题可以采用贪心的做法。对于一个已经确定的最优子链条,如何选择一个最优的新数对接上去?答案:我们根据数对的第二个数,对数对数组进行升序排序,得到有序的数组arr
。我们记当前已经确定的数对链条的最后一个数对的值为[a,b]
,那么我们需要在arr中找到一个数对[x,y],在满足x > b的情况下,y是最小的(这里利用有序性,直接遍历,检查是否x > b,第一个满足条件的数对,就是y最小数对)。然后按这个思路,不断的寻找新的最优的新数对即可。
关于贪心方法正确性的证明,假设对于当前最优子链条,能找到更优的新数对[x1,y1],那么y1 必然大于按贪心方法找到的 y(我们在之前的定义中,定义y为找到的第一个符合条件的数对)。如果y1 > y, x1 > b 同时成立,那么数对[x, y]必然可以替换[x1, y1],插入到最优链中。这实际上是矛盾的。因此,按贪心方法即能找到最优的数链。
class Solution { public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, (o1, o2)-> o1[1] - o2[1]); int cnt = 1; int[] prevElement = pairs[0]; for(int i = 0; i < pairs.length; i++){ if(pairs[i][0] > prevElement[1]){ cnt ++; prevElement = pairs[i]; } } return cnt; } }