LeetCode 1024. 视频拼接
题目描述
题意分析
从给定视频片段中选择尽量少的片段，完整覆盖从
0到time的连续时间范围。片段允许重叠，也可以裁剪掉多余部分，但不能留下任何时间空隙；无法覆盖时返回-1。若已经连续覆盖到某个位置，下一段的起点必须不晚于这个位置，才能无缝接上。在所有能够接入的候选中，应选择终点最远的片段，让同样一次选择带来最大的覆盖进展。
解法：排序后贪心扩展最远覆盖
核心思路
[!blue]
先按片段起点升序排序，用
curEnd表示已经用ans个片段连续覆盖到的位置，用idx指向尚未检查的片段。开始时还没选任何片段，只覆盖起点0。每轮固定
curEnd，扫描所有起点不超过它的片段，用nextEnd记录这些候选能到达的最远终点。起点等于当前终点也可以衔接，已经结束在覆盖范围内的片段则不会带来新的进展。为什么选最远终点是安全的？任何接续方案的下一段都必须从当前覆盖范围内开始；把它替换为本轮终点最远的候选，只会扩大已覆盖范围，不会失去原来能接上的后续片段。因此在相同片段数量下尽量覆盖得远，不会比其他选择需要更多片段。
扫描完本轮候选后才增加一次
ans，并令curEnd = nextEnd。内层不能一边扫描一边更新curEnd，否则新扩大的范围可能又接入更多片段，相当于连续使用多段，却只增加一次计数。已经扫描过的候选不需要重新考虑：它们的终点都不超过上轮选出的
curEnd，以后不可能继续延伸覆盖。代码中的nextEnd保留上一轮值，而上一轮结束时它正好等于新的curEnd，因此每轮都从当前覆盖位置继续求更远终点。若全部可接入片段都无法让
nextEnd超过curEnd，后面未扫描片段的起点又都更晚，必然存在无法跨越的空隙，返回-1。覆盖到time或更远就结束；超出的部分可裁剪，不必恰好停在终点。
解题步骤
- 按起点升序排序片段，初始化片段数、扫描下标和两个覆盖边界为零。
- 当前覆盖仍未到达
time时，固定curEnd扫描所有起点不大于它的片段。- 用这些片段的最大终点更新
nextEnd，每个片段只向前扫描一次。- 如果不能向前推进，返回
-1；否则片段数加一，确认curEnd = nextEnd。- 完成覆盖后返回片段数；目标长度为零时无需选片段。
代码实现
class Solution {
public int videoStitching(int[][] clips, int time) {
Arrays.sort(
clips,
(a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return b[1] - a[1];
});
int ans = 0;
int idx = 0;
int curEnd = 0;
int nextEnd = 0;
while (curEnd < time) {
// 固定当前边界，扫描全部可接入候选后只选择一段。
while (idx < clips.length && clips[idx][0] <= curEnd) {
nextEnd = Math.max(nextEnd, clips[idx][1]);
idx++;
}
// 所有候选都无法延伸，后续片段更无法跨过缺口。
if (nextEnd == curEnd) {
return -1;
}
ans++;
curEnd = nextEnd;
}
return ans;
}
}
import "sort"
func videoStitching(clips [][]int, time int) int {
sort.Slice(clips, func(i, j int) bool {
if clips[i][0] != clips[j][0] {
return clips[i][0] < clips[j][0]
}
return clips[i][1] > clips[j][1]
})
ans := 0
idx := 0
curEnd := 0
nextEnd := 0
for curEnd < time {
// 固定当前边界，扫描全部可接入候选后只选择一段。
for idx < len(clips) && clips[idx][0] <= curEnd {
if clips[idx][1] > nextEnd {
nextEnd = clips[idx][1]
}
idx++
}
// 所有候选都无法延伸，后续片段更无法跨过缺口。
if nextEnd == curEnd {
return -1
}
ans++
curEnd = nextEnd
}
return ans
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，排序后所有片段只扫描一次。
- 空间复杂度：扫描 $O(1)$；Java 对象数组排序辅助空间 $O(n)$，Go 排序栈 $O(\log(n+1))$。
关键点总结
[!green]
- curEnd 在整轮候选扫描中保持不变，选完才推进。
- 起点等于当前终点也能衔接。
- 此实现会按起点重新排列输入片段。
易错点总结
[!yellow]
- 每扫描一个候选就计一次，会把未采用的片段也算进去。
- 内层同步扩大 curEnd，会一轮串用多段却只计一次。
- 没有无法推进的判断，存在空隙时循环不会结束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 45. 跳跃游戏 II | 中等 | 同样按当前可达右边界分层，并在这一层所有候选中尽量扩远，层数对应最少片段数。 |
| 1326. 灌溉花园的最少水龙头数目 | 困难 | 同样用尽量少的区间覆盖整段连续范围，原题区间由水龙头位置和半径产生。 |