leetcode 646 Maximum Length of Pair Chain 详细解答
leetcode 646 Maximum Length of Pair Chain 详细解答
解法1
通过观察,我们想找到一个最长的序列,满足题目的条件,由此容易想到用动态规划(最长子序列问题一般都可以用动态规划)。
状态转移方程:
具体代码如下:
时间复杂度:O(N2),空间复杂度:O(N)
解法2
贪心算法
大家可以思考一下,以数组 [ [1, 4], [0, 6], [2, 6], [5, 6] ]为例
以为第1个数字为排序指标,则结果是:
0-----------------6
1------4
2---------6
5----6
以为第2个数字为排序指标,则结果是:
1-----4
0-----------------6
2----------6
5-----6
通过上述的比较则可以看出来,第一种情况,无法根据排序直接得出结果,第二种情况就可以用贪心,用区间的结尾去和下一个区间的开头进行比较。得到最优解。
代码如下: