0646：最长数对链（★）

力扣第 646 题

题目

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < 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 <= lefti < righti <= 1000

相似问题：

• 0300：最长递增子序列
• 0491：非递减子序列
• 2771：构造最长非递减子数组（1791 分）

分析

类似 0435，贪心地选第二个数最小的数对即可。

解答

1
2
3
4
5
6
7
8

def findLongestChain(self, pairs: List[List[int]]) -> int:
    pairs.sort(key=lambda x: x[1])
    res, end = 0, float('-inf')
    for s, e in pairs:
        if s>end:
            res += 1
            end = e
    return res

56 ms