646.maximum-length-of-pair-chain.md

646. Maximum Length of Pair Chain

Greedy

Sorted By end

Similar to 435. Non-overlapping Intervals, but instead of removing overlapping intervals, we want to keep the maximum number of non-overlapping pairs, we can use greedy approach to solve this problem. We always pick the interval that ends earliest greedily.

fun findLongestChain(pairs: Array<IntArray>): Int {
    pairs.sortBy { it[1] }
    var nonOverlap = 1
    var previousRight = pairs.first()[1]
    for (i in 1 until pairs.size) {
        val (left, right) = pairs[i]
        if (previousRight < left) {
            nonOverlap++
            previousRight = right
        }
    }
    return nonOverlap
}

Sorted By left

What if we sort by left? It's not always correct. Consider the case below:

[1, 10], [2, 3], [4, 5] [6, 7]

We will choose [1, 10] and drop the remaining pairs based on our greedy approach, but the correct answer is [2, 3], [4, 5], [6, 7]. We need some tweaks to make it work. (Also similar to 435. Non-overlapping Intervals)

fun findLongestChain(pairs: Array<IntArray>): Int {
    pairs.sortBy { it[0] }
    var nonOverlap = 1
    var previousRight = pairs.first()[1]
    for (i in 1 until pairs.size) {
        val (left, right) = pairs[i]
        if (previousRight < left) {
            nonOverlap++
            previousRight = right
        } else {
            previousRight = minOf(previousRight, right)
        }
    }
    return nonOverlap
}

• Time Complexity: O(n lg n).
• Space Complexity: O(lg n).

The dynamical programming solution is not optimal, might skip it.

Top-Down DP

private val memo = HashMap<Int, Int>()

fun findLongestChain(pairs: Array<IntArray>): Int {
    Arrays.sort(pairs) { p1, p2 -> p1[0] - p2[0] }
    for (i in 0 until pairs.size) {
        topDown(pairs, i)
    }
    var result = 1
    for (value in memo.values) {
        result = maxOf(result, value)
    }
    return result
}

private fun topDown(pairs: Array<IntArray>, i: Int): Int {
    if (memo.containsKey(i)) return memo[i]!!
    var maxLength = 1
    for (j in 0 until i) {
        if (pairs[j][1] < pairs[i][0]) {
            maxLength = maxOf(maxLength, 1 + topDown(pairs, j))
        }
    }
    memo[i] = maxLength
    return maxLength
}

• Time Complexity: O(n^2).
• Space Complexity: O(n).

Bottom-Up DP

fun findLongestChain(pairs: Array<IntArray>): Int {
    Arrays.sort(pairs) { p1, p2 -> p1[0] - p2[0] }

    val dp = IntArray(pairs.size) { 1 }
    var maxLength = 1
    for (i in 0 until pairs.size) {
        for (j in 0 until i) {
            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = maxOf(dp[i], 1 + dp[j])
            }
        }
        maxLength = maxOf(maxLength, dp[i])
    }
    return maxLength
}

• Time Complexity: O(n^2).
• Space Complexity: O(n).