What is the main pattern used in Maximum Length of Pair Chain?

The problem primarily uses state transition dynamic programming, combined with greedy sorting to efficiently build the longest chain.

Can this problem be solved without dynamic programming?

Yes, a greedy approach after sorting by the second element can achieve O(n log n) time while maintaining correctness.

What common mistakes should I avoid?

Do not skip sorting, forget the b < c condition, or incorrectly extend chains without tracking the last end.

What is the time complexity for the DP approach?

Sorting is O(n log n), and evaluating all previous pairs in DP makes it O(n^2). Greedy reduces evaluation to O(n).

How do I track the longest chain efficiently?

Maintain either a DP array for state transitions or a single variable for the last chain end during greedy iteration.

#646

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长数对链

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [left i , right i ] 且 left i i 。现在，我们定义一种跟随关系，当且仅当 b 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造数对链。…

数组动态规划贪心排序

题目描述

给你一个由 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

lightbulb

解题思路

方法一：排序 + 贪心

我们将所有数对按照第二个数的升序排序，用一个变量 $\textit{pre}$ 维护已经选择的数对的第二个数的最大值。

遍历排序后的数对，如果当前数对的第一个数大于 $\textit{pre}$ ，那么我们可以贪心地选择当前数对，答案加一，并将 $\textit{pre}$ 更新为当前数对的第二个数。

遍历结束后，返回答案即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数对的数量。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        ans, pre = 0, -inf
        for a, b in pairs:
            if pre < a:
                ans += 1
                pre = b
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on sorting pairs by the second element to simplify chain selection.
question_mark
Expect a DP or greedy approach based on the state transition dynamic programming pattern.
question_mark
Be prepared to discuss time vs space trade-offs between O(n^2) DP and O(n log n) greedy solution.

warning

常见陷阱

外企场景

error
Failing to sort pairs first can lead to incorrect chain lengths.
error
Incorrectly updating DP table without checking b < c condition.
error
Mixing up greedy selection order can produce invalid chains.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the longest decreasing chain by reversing pair comparisons.
arrow_right_alt
Allow overlapping chains and count maximum compatible subsets instead of strict chains.
arrow_right_alt
Extend to 3D triplets where each subsequent element must be larger in all dimensions.

help

常见问题

外企场景

继续练习

#435 无重叠区间 #1262 可被三整除的最大和 #1363 形成三的最大倍数