题目描述
思路解析动画文字版
记住这句：last 记每个起点的最远延伸，贪心扫描时走到当前段右端就接一段、跳到段内最远 mx。后面每帧都在套它。
先开一个长度 10 的数组 last，last[i] 记「从位置 i 起跳一步最远能到哪」，一开始都填 0。
看片段 [0,2]：从位置 0 起跳能延伸到 2，比原来的 0 远，last[0] 更新成 2。
看片段 [4,6]：从位置 4 起跳能延伸到 6，比原来的 0 远，last[4] 更新成 6。
看片段 [8,10]：从位置 8 起跳能延伸到 10，比原来的 0 远，last[8] 更新成 10。
看片段 [1,9]：从位置 1 起跳能延伸到 9，比原来的 0 远，last[1] 更新成 9。
看片段 [1,5]：位置 1 已经能到 9，比 5 更远或相等，last[1] 保持不变。
看片段 [5,9]：从位置 5 起跳能延伸到 9，比原来的 0 远，last[5] 更新成 9。
last 数组建好了。接下来从左往右扫，用 pre 记当前段右端（起步 0），mx 记这一段内能延伸到的最远。绿色格子代表已经覆盖到的位置。
位置 0 能从某个起点延伸到 2，把这一段内的最远 mx 抬到 2。
恰好走到当前段的右端 pre = 0，必须接一段新片段：ans 加到 1，把覆盖边界一口气推到这一段攒出的最远 2。
位置 1 能从某个起点延伸到 9，把这一段内的最远 mx 抬到 9。
位置 2 的起跳 last[2] = 0 到不了更远，mx 还是 9，继续往右走。
恰好走到当前段的右端 pre = 2，必须接一段新片段：ans 加到 2，把覆盖边界一口气推到这一段攒出的最远 9。
位置 3 的起跳 last[3] = 0 到不了更远，mx 还是 9，继续往右走。
位置 4 的起跳 last[4] = 6 到不了更远，mx 还是 9，继续往右走。
位置 5 的起跳 last[5] = 9 到不了更远，mx 还是 9，继续往右走。
位置 6 的起跳 last[6] = 0 到不了更远，mx 还是 9，继续往右走。
位置 7 的起跳 last[7] = 0 到不了更远，mx 还是 9，继续往右走。
位置 8 能从某个起点延伸到 10，把这一段内的最远 mx 抬到 10。
位置 9 的起跳 last[9] = 0 到不了更远，mx 还是 10，继续往右走。
恰好走到当前段的右端 pre = 9，必须接一段新片段：ans 加到 3，把覆盖边界一口气推到这一段攒出的最远 10。
扫完，覆盖边界 pre 已经到 10，盖住了整段 [0, 10]。一路接了 3 段，所以答案就是 3。
边界先想清：起点不含 0、中途断层、单段覆盖全程这三种情形。
面试重点：认出它就是跳跃游戏式的最少覆盖。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def videoStitching(self, clips: List[List[int]], time: int) -> int: last = [0] * time for a, b in clips: if a < time: last[a] = max(last[a], b) ans = mx = pre = 0 for i, v in enumerate(last): mx = max(mx, v) if mx <= i: return -1 if pre == i: ans += 1 pre = mx return ans复杂度
- 时间：O(n + time)，建 last 表扫 n 个片段，再线性扫 time 个位置
- 空间：O(time)，一个长度 time 的 last 数组
易错点
面试追问把动画讲成自己的话
追问这题和「跳跃游戏 II（LeetCode 45）」是一回事吗？
追问能不能用动态规划做？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长等差数列
LeetCode 1027 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题