646. 最长数对链

题目描述

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [left_i, right_i] 且 left_i < right_i。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 1：

输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。

示例 2：

输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

提示：

n == pairs.length
1 <= n <= 1000
-1000 <= left_i < right_i <= 1000

解法一：排序 + 动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func findLongestChain(pairs [][]int) int {
    n := len(pairs)
    sort.Slice(pairs, func(i, j int) bool {
        return pairs[i][0] < pairs[j][0] || pairs[i][0] == pairs[j][0] && pairs[i][1] < pairs[j][1]
    })
    // dp[i] 表示在排序后的 pairs 中，以 pairs[i] 结尾最长数对链的长度
    dp, ans := make([]int, n), 1
    dp[0] = 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if pairs[i][0] > pairs[j][1] && dp[j] > dp[i] {
                dp[i] = dp[j]
            }
        }
        dp[i] += 1
        if dp[i] > ans {
            ans = dp[i]
        }
    }
    return ans
}