646. 最长数对链 - Kotlin 动态规划+贪心

原题地址：https://leetcode.cn/problems/maximum-length-of-pair-chain/

题解

方法一：动态规划

将pairs进行排序，然后用一个数组dp记录以pairs[i]结尾的最长数链

令j遍历0到i，当j[1]<i[0]时，说明i可以接在以j结尾的最长数链后形成一个更长的数链

此时dp[i]=dp[j]+1，记录最大的dp[i]即为答案

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    fun findLongestChain(pairs: Array<IntArray>): Int {
        pairs.sortBy { a -> a[0] }
        val dp = Array(pairs.size) { 1 }
        var max = 1
        for (i in 0 until pairs.size) {
            for (j in 0 until i) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = if (dp[i] < dp[j] + 1) dp[j] + 1 else dp[i]
                    max = if (max < dp[i]) dp[i] else max
                }
            }
        }
        return max
    }
}

方法二：贪心

和会议安排类似，将pairs按照右边界进行升序排序

当每次都在满足条件的数对中选右边界最小的数对构成数链时，最后的结果自然是最优的

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun findLongestChain(pairs: Array<IntArray>): Int {
        pairs.sortBy { a -> a[1] }
        var max = 0
        var rightWall=Int.MIN_VALUE
        for (i in 0 until pairs.size) {
            if(pairs[i][0]>rightWall){
                rightWall=pairs[i][1]
                max++
            }
        }
        return max
    }
}