LeetCode 646中等DP/贪心
最长数对链 图解题解
这道题到底在问什么
给定数对数组 pairs，每个数对是 [left, right] 且 left < right。若数对 a 的 right < 数对 b 的 left，则 a 可接到 b 前面。返回能接成的最长链的长度。
- 输入
- pairs=[[1,2],[2,3],[3,4]]
- 输出
- 2 （[1,2] 接 [3,4]，2 不能接 [2,3] 因为 2 不小于 2）
- 输入
- pairs=[[1,2],[7,8],[4,5]]
- 输出
- 3 （[1,2] 接 [4,5] 接 [7,8]）
最优解：一步一步想明白
- 3记住这套「按右端点排序，左端点能越过 end 就接、否则跳」，下面每一帧都在套它。
- 4先看原始 8 个数对，右端点是乱的：[1,2]、[7,8]、[4,5]、[2,3]、[5,6]、[3,4]、[6,7]、[1,9]。贪心的前提是把它们按右端点排好。
- 5按右端点从小到大排好：[1,2]、[2,3]、[3,4]、[4,5]、[5,6]、[6,7]、[7,8]、[1,9]。这条轴上每个数字就是对应数对的右端点，左端点写在讲解里。现在从左往右贪心扫。
- 6开局：还没接任何数对，把 end 设成极小（这样第一个数对一定能接进来），链长 ans=0。从最左边那个数对开始看。
- 7轮到数对 [1,2]（紫色，右端点 2）。它能不能接到链尾，只看它的左端点 1 是否严格大于当前 end = 负无穷。绿色是已接入的，灰色是已跳过的。
- 81 严格大于 end，能接！把 [1,2] 接进链（变绿），链长涨到 1，并把 end 更新成它的右端点 2（下一个数对要越过的就是这个新门槛）。
- 9轮到数对 [2,3]（紫色，右端点 3）。它能不能接到链尾，只看它的左端点 2 是否严格大于当前 end = 2。绿色是已接入的，灰色是已跳过的。
- 102 没有严格大于 end = 2，接上去会和链尾重叠（红色），跳过 [2,3]。注意：它的右端点不比当前 end 小，留着它只会更挤，丢掉不亏。end 保持 2。
- 11轮到数对 [3,4]（紫色，右端点 4）。它能不能接到链尾，只看它的左端点 3 是否严格大于当前 end = 2。绿色是已接入的，灰色是已跳过的。
- 123 严格大于 end，能接！把 [3,4] 接进链（变绿），链长涨到 2，并把 end 更新成它的右端点 4（下一个数对要越过的就是这个新门槛）。
- 13轮到数对 [4,5]（紫色，右端点 5）。它能不能接到链尾，只看它的左端点 4 是否严格大于当前 end = 4。绿色是已接入的，灰色是已跳过的。
- 144 没有严格大于 end = 4，接上去会和链尾重叠（红色），跳过 [4,5]。注意：它的右端点不比当前 end 小，留着它只会更挤，丢掉不亏。end 保持 4。
- 15轮到数对 [5,6]（紫色，右端点 6）。它能不能接到链尾，只看它的左端点 5 是否严格大于当前 end = 4。绿色是已接入的，灰色是已跳过的。
- 165 严格大于 end，能接！把 [5,6] 接进链（变绿），链长涨到 3，并把 end 更新成它的右端点 6（下一个数对要越过的就是这个新门槛）。
- 17轮到数对 [6,7]（紫色，右端点 7）。它能不能接到链尾，只看它的左端点 6 是否严格大于当前 end = 6。绿色是已接入的，灰色是已跳过的。
- 186 没有严格大于 end = 6，接上去会和链尾重叠（红色），跳过 [6,7]。注意：它的右端点不比当前 end 小，留着它只会更挤，丢掉不亏。end 保持 6。
- 19轮到数对 [7,8]（紫色，右端点 8）。它能不能接到链尾，只看它的左端点 7 是否严格大于当前 end = 6。绿色是已接入的，灰色是已跳过的。
- 207 严格大于 end，能接！把 [7,8] 接进链（变绿），链长涨到 4，并把 end 更新成它的右端点 8（下一个数对要越过的就是这个新门槛）。
- 21轮到数对 [1,9]（紫色，右端点 9）。它能不能接到链尾，只看它的左端点 1 是否严格大于当前 end = 8。绿色是已接入的，灰色是已跳过的。
- 221 没有严格大于 end = 8，接上去会和链尾重叠（红色），跳过 [1,9]。注意：它的右端点不比当前 end 小，留着它只会更挤，丢掉不亏。end 保持 8。
- 23扫完全部 8 个数对，绿色这 4 个就是接成的最长链：[1,2] → [3,4] → [5,6] → [7,8]。灰掉的都是接不进来的。答案 4。
⚠️ 容易写错的地方
✗ 错：按左端点排序
✓ 对：按右端点排序
贪心要让链尾右端点尽量小，才给后面留最大空间；按左端点排会漏最优解
✗ 错：把「可接」写成 a ≥ end
✓ 对：a > end（严格）
题目要求前一个 right 严格小于后一个 left，相等不能接
✗ 错：end 初值设为 0
✓ 对：设成极小值
数对可能含负数，初值不够小会让第一个数对接不进来
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda x: x[1])
ans = 0
end = -10**18
for a, b in pairs:
if a > end:
ans += 1
end = b
return ansC++
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
int ans = 0, end = INT_MIN;
for (auto &p : pairs) if (p[0] > end) { ans++; end = p[1]; }
return ans;
}
};Java
import java.util.*;
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
int ans = 0, end = Integer.MIN_VALUE;
for (int[] p : pairs) if (p[0] > end) { ans++; end = p[1]; }
return ans;
}
}复杂度
时间
O(n log n)
排序占主导，之后扫描只 O(n)
空间
O(1)
只用 ans、end 两个变量（排序原地）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最长数对链 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题也能用动态规划，和贪心比怎么选？+
DP 思路是按左端点排序后求「最长上升子序列」，转移 O(n^2) 或配二分到 O(n log n)。贪心（按右端点排 + 一遍扫）同样 O(n log n) 但代码更短、常数更小，是这题首选。面试两种都说清楚加分。
它和「无重叠区间 LC435」是同一类吗？+
是同一套贪心模板。LC435 求最少删几个区间使剩下不重叠，等价于求「最多保留多少互不重叠区间」，也是按右端点排序贪心；本题的「严格小于才能接」对应那题的「区间端点不重叠」，把不等号口径对齐即可互相转化。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最长数对链 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。