视频拼接

视频拼接这道题到底要拼什么

给一堆视频片段，每段 clips[i]=[start,end] 是一段时间区间，可自由再剪辑。求最少几段拼满 [0,time]，拼不出返回 -1。例 clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]、time=10，取 [0,2]、[1,9]、[8,10] 拼满，答案 3。

挨个决定每段选不选，为什么会指数爆

n 个片段各选或不选，有 2ⁿ 种组合（2ⁿ 即 2 的 n 次方，随片段数翻倍涨），逐一验证哪种拼满就数不完，且组合间前半截大量重叠、反复重算。改成只盯每个位置一步最远到哪，一遍扫过即压成线性。

last[i] 记什么，为什么这道题能当跳跃游戏跳

先建长度 time 的数组 last，last[i] 存『从位置 i 起跳一步最远到哪』：起点为 i 的片段取 end 最大，即 a 小于 time 时 last[a]=max(last[a], b)。如 [1,9] 与 [1,5] 都从 1 起跳，last[1] 取 9。

于是成了跳跃游戏式覆盖：站在位置 i 一步跳到 last[i]，从 0 出发用最少几跳盖到 time，每步跳尽量远即贪心（贪心＝只挑当下够得着的最远，不回头）。

从左扫时，为什么非等到走到段右端才接一段

从左往右扫，带三个量：ans 记已接段数、pre 记当前段右边界（起步 0）、mx 记至今能延伸到的最远处。每走一格先 mx=max(mx, v) 撑大最远。

再看两件事：mx 不大于当前位置，说明追不过脚下就返回 -1；pre 等于当前位置，说明到段尽头，ans 加一、pre 推到 mx。没到 pre 时只攒 mx——接段只在段右端那一下，早接多算一段、晚接漏了覆盖。

拿题面示例把 last 建好、再扫一遍

先建 last：last[0]=2、last[4]=6、last[8]=10、last[1]=9（[1,5] 的 5 输给 9），last[5]=9，得 last=[2,9,0,0,6,9,0,0,10,0]。

再扫，ans=mx=pre=0。位置 0：mx 到 2、pre 追平，接第一段，ans=1、pre=2。位置 1：mx 撑到 9，pre 未到不接段。位置 2：mx 已到 9、pre 追平 2，接第二段，ans=2、pre=9。位置 3 到 8 只有位置 8 把 mx 推到 10，pre=9 无格追平。位置 9：pre 追平 9，接第三段，ans=3、pre=10，答案 3。

漏了那一判，拼不出的输入为什么会诈出假答案

建 last、再扫 time 个位置都是线性，合起来 O(n+time)（大 O 记号，描述数据变大时步数怎么涨）；只一个 last 数组，空间 O(time)。

几处最易写错。漏掉『追不过当前位置就返回 -1』最坑：本该无解的输入就吐出假段数。last 长度取 time 而非 time+1，只扫到 time-1。计数只在 pre 到段右端加一，写成一遇更远 mx 就加会把一段拆成几段。边界三种：起点不含 0（last[0]=0 立即返 -1）、中途断层跨不过缺口、单段覆盖全程（答案 1）。