Leetcode - Maximum Length of Pair Chain

https://leetcode.com/problems/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: 2
Explanation: The longest chain is [1,2] -> [3,4]

func findLongestChain(pairs [][]int) int {
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i][0] < pairs[j][0]
    })
    if len(pairs) <= 1 {
        return len(pairs)
    }
    dp := make([]int, len(pairs))
    dp[0] = 1
    for i := 1; i < len(pairs); i++ {
        max := 1
        for j := 0; j < i; j++ {
            if pairs[j][1] < pairs[i][0] {
                tmp := dp[j] + 1
                if tmp > max {
                    max = tmp
                }
            }
        }
        dp[i] = max
    }
    max := math.MinInt32
    for _, n := range dp {
        if max < n {
            max = n
        }
    }
    return max
}

• 相关文章
• 全局相关文章