LeetCode 646. 最长数对链
题目描述
题意分析
可以从数对中选择一部分并任意重排，求能组成的最长链。若前一个数对为
[a, b]，下一个为[c, d]，必须满足b < c；端点相等也不能连接。
解法：按右端点排序的贪心
核心思路
[!blue]
在当前能够连接的数对中，优先选择右端最小的。 每加入一个数对，后续只能使用左端更大的数对；新右端越小，给后续留下的选择就越多。先按右端升序排序，就能在扫描时直接找到这样的候选。这个选择可用交换证明。固定已经选好的链，设贪心接下来选 $G$，某个最优延长方案的下一项是 $O$。两者都能接在当前链后，且 $G$ 的右端不大于 $O$；将 $O$ 换成 $G$ 后，原来能接在 $O$ 后的数对也仍能接在 $G$ 后，链长不变。因此总有一个最优方案采用本次贪心选择，反复应用即可得到最长链。
curEnd保存已选链最后一项的右端，count保存长度。当前左端严格大于curEnd就加入并更新两者，否则跳过。由于按右端排序，被跳过的当前数对不会比已选末端结束得更早，替换它也无法增加后续机会。空链的末端要初始化为小于所有合法端点的值，让第一个数对自然被选中，负数端点也能正确处理。排序只改变数对的处理顺序，不改变每个数对内部的左右端含义。
解题步骤
- 按右端点升序排序。
- 初始化空链和足够小的末端。
- 当前左端严格超过末端时，增加长度并更新末端。
- 返回链长。
代码实现
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
int count = 0;
int curEnd = Integer.MIN_VALUE;
for (int[] pair : pairs) {
// 端点相等不能连接，只有严格超过末端才选择当前数对。
if (pair[0] > curEnd) {
count++;
curEnd = pair[1];
}
}
return count;
}
}
import "sort"
func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][1] < pairs[j][1]
})
count := 0
curEnd := -1 << 60
for _, pair := range pairs {
// 端点相等不能连接，只有严格超过末端才选择当前数对。
if pair[0] > curEnd {
count++
curEnd = pair[1]
}
}
return count
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，排序后扫描。
- 空间复杂度：扫描辅助空间 $O(1)$；Java 对象数组排序工作区为 $O(n)$，Go 排序栈为 $O(\log(n+1))$，输入会被重排。
关键点总结
[!green]
- 结束更早不会减少未来接续机会。
- 可以重排数对，因此排序不破坏题目要求。
- 接续是严格不等，端点相同不能连接。
易错点总结
[!yellow]
- 按左端最早就选：左端早但右端很晚的数对，可能挡住后面多组本可连接的数对。
- 末端初值为零：负数端点可能全部被跳过。
- 接续使用大于等于：接受题目不允许的端点相接。
- 未选中也更新末端：破坏已选链的真实状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 435. 无重叠区间 | 中等 | 同样按结束位置贪心选最多区间，但本题衔接要求严格小于，原题常允许端点相接。 |
| 300. 最长递增子序列 | 中等 | 同样求最长可衔接链，本题前项结束值小于后项开始值，非单个值之间的递增关系。 |
| 452. 用最少数量的箭引爆气球 | 中等 | 按结束位置判断区间重叠并进行贪心选择；本题将数对连接视为不重叠区间选择，该题用最少位置覆盖所有区间。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！