1. 项目概述从“视频拼接”到“区间覆盖”的算法思维跃迁第一次看到“视频拼接”这个标题你可能会下意识地想到视频编辑软件里的时间轴拖动、裁剪、合并片段。但在算法世界里LeetCode第1024题“视频拼接”却是一个披着生活外衣的经典算法问题。它不关心视频编码格式也不处理像素数据它的核心是区间覆盖。想象一下你手头有一堆长短不一的视频片段每个片段有确定的开始和结束时间你的目标是用最少的片段无缝拼接出一段从0时刻到目标时间T的完整视频。这本质上就是在一条时间线上用给定的区间视频片段去覆盖一个更大的目标区间[0, T]。这个问题之所以经典且被选入LeetCode是因为它完美地将一个实际场景抽象成了一个可被计算机高效求解的模型。它考察的是对贪心算法的深刻理解以及对区间类问题的预处理和遍历技巧。无论是准备技术面试还是希望提升解决实际规划类问题的能力吃透这道题都能让你获益匪浅。它适合所有正在学习算法与数据结构尤其是对贪心策略和区间问题感到困惑的开发者。接下来我将带你深入拆解这道题从问题本质、思路推导、代码实现到避坑指南完整走一遍。2. 核心思路拆解为什么贪心策略是正解面对“视频拼接”一个最朴素的想法可能是回溯或动态规划尝试所有片段的组合看哪个组合能覆盖[0, T]且用的片段最少。这在片段数量少时可行但一旦数据量增大时间复杂度将呈指数级爆炸。我们必须寻找更优解。仔细分析问题特性我们可以发现两个关键点这直接指向了贪心算法目标区间是固定的我们要覆盖的是从0到T的连续区间起点是0。我们关心的是“最远能延伸到哪”在选择片段时对于一个已经覆盖到的位置i我们希望在所有起点小于等于i的片段中选择一个结束时间最晚的片段。因为结束时间越晚它一次性覆盖的范围就越大就越有可能用更少的片段到达T。这引出了解决此问题的核心贪心策略我们维护一个当前覆盖到的最远位置last。在每一轮中我们遍历所有起点小于等于last的片段从中选出结束时间最大的那个用它来更新last相当于将这段视频拼接到时间线上同时增加片段计数。重复这个过程直到last达到或超过T或者无法再找到可以扩展last的片段。注意这里有一个至关重要的预处理步骤。为了能高效地找到“起点小于等于last的片段中结束时间最晚的”我们通常不直接遍历clips数组。一个更聪明的做法是预处理一个数组maxEnd[i]表示所有以时间点i为起点的片段中最大的结束时间是多少。如果没有任何片段以i为起点则maxEnd[i] i即无法延伸。这个预处理能将每次寻找“最远可到达位置”的操作降到O(1)复杂度。为什么贪心在这里能保证最优解我们可以用反证法简单理解假设在某一步我们根据贪心策略选择了一个结束时间为E1的片段A而存在另一个结束时间为E2E2 E1的片段B可选但我们没选。那么选择A之后我们到达的位置是E1后续我们需要更多的片段才能从E1走到T。而如果当初选择了B我们直接就到了E2E2 E1从E2走到T可能需要的片段数更少或相等。因此不选结束时间最远的片段不可能得到更优片段数更少的解。这个“选择当前可及范围内结束最晚的区间”的策略被证明是解决这类“最小区间覆盖”问题的标准贪心解法。3. 算法实现与代码详解理解了贪心策略我们来看具体的代码实现。我将以Python为例提供两种常见的实现方式并详细解释每一步的意图。3.1 方法一预处理 贪心遍历标准解法这是最清晰、效率也较高的方法时间复杂度O(T N)其中N是片段数量T是目标时间。def videoStitching(clips, T): :type clips: List[List[int]] :type T: int :rtype: int # 1. 预处理创建maxEnd数组 # 数组长度为 T1 就足够了因为超过T的时间点我们不需要关心 maxEnd [0] * (T 1) for start, end in clips: # 只记录起点在[0, T]范围内的片段并且只关心其结束时间对起点的影响 if start T: # 对于同一个起点我们只保留最远的结束时间 maxEnd[start] max(maxEnd[start], end) # 2. 贪心遍历 prev_end 0 # 上一段视频结束的位置即当前已覆盖区间的右端点 curr_end 0 # 在当前所有“起点prev_end”的片段中能到达的最远位置 count 0 # 使用的片段数量 i 0 # 遍历时间点注意我们只需要遍历到 T-1因为当prev_end T时任务就完成了 while i T: # 对于当前时间点i更新“从i及之前的位置出发能到达的最远位置” curr_end max(curr_end, maxEnd[i]) # 关键判断如果当前时间点i 等于 上一段结束的位置prev_end # 意味着我们无法再向前推进了没有片段能覆盖这个缺口 if i prev_end: # 如果此时最远能到的位置curr_end 没有超过i说明卡住了无法覆盖 if curr_end i: return -1 # 否则我们选择一个新的片段它的起点在prev_end之前终点是curr_end # 这个片段帮助我们覆盖了 [prev_end, curr_end] 这部分区间 count 1 prev_end curr_end # 更新已覆盖的右端点 # 如果prev_end已经达到或超过T提前结束循环 if prev_end T: break i 1 # 循环结束后检查是否成功覆盖 return count if prev_end T else -1代码逐行解析预处理 (maxEnd数组)maxEnd[i]存储了所有以i为起点的片段中最大的结束时间。例如片段[0,2]和[0,4]都会影响maxEnd[0]最终maxEnd[0] 4。三个核心变量prev_end可以理解为“当前已拼好的视频的结束时间点”。在贪心选择中当我们决定使用一个新片段时prev_end会更新为这个新片段的结束时间。curr_end在遍历过程中它动态维护着“从当前位置i及之前的所有位置出发能到达的最远位置”。它通过maxEnd[i]不断更新。count记录使用的片段数。贪心选择时机当遍历的指针i追上prev_end时i prev_end说明上一段视频已经播放完了我们必须开始选择一个新的片段来接上。此时curr_end的值就代表了所有“起点在prev_end及之前”的片段中能带我们去到的最远地方。我们选择这个能带我们去curr_end的片段虽然代码中没有显式记录是哪个片段但这个动作在逻辑上发生了。无法覆盖的判断如果在i prev_end时发现curr_end i意味着没有哪个片段的起点小于等于i且结束时间大于i时间线在这里断掉了无法完成拼接返回-1。3.2 方法二排序 贪心另一种思路是先将片段按起点升序终点降序排序然后进行一轮贪心遍历。这种方法更直观地体现了“在可选的片段里选结束最晚的”这一过程。def videoStitching(clips, T): # 1. 排序先按起点升序起点相同的按终点降序 clips.sort(keylambda x: (x[0], -x[1])) count 0 curr_end 0 # 当前已覆盖的最远位置 next_end 0 # 下一个待选片段能到达的最远位置 i 0 n len(clips) while i n and curr_end T: # 2. 如果当前片段的起点已经超过了当前能覆盖到的最远位置(curr_end) # 说明出现了断层无法继续拼接 if clips[i][0] curr_end: return -1 # 3. 在所有“起点 curr_end”的片段中寻找能到达的最远位置 while i n and clips[i][0] curr_end: next_end max(next_end, clips[i][1]) i 1 # 4. 选择结束时间最远的那个片段逻辑上 count 1 curr_end next_end # 用找到的最远位置更新当前覆盖范围 # 5. 检查最终是否覆盖了目标区间 return count if curr_end T else -1两种方法对比特性方法一预处理遍历方法二排序贪心时间复杂度O(T N)O(N log N) (主要开销在排序)空间复杂度O(T) (用于maxEnd数组)O(1) 或 O(log N) (排序栈空间)优点当T不大时非常高效逻辑清晰一次遍历解决问题。不依赖T的大小当T很大而N较小时有优势。代码更贴近贪心思想的原始表述。缺点如果T非常大例如10^9而片段数N很小创建长度为T的数组不现实。排序增加了时间复杂度对于区间问题排序是常见操作。适用场景面试推荐、T的范围已知且合理如本题常见T100。T的范围未知或极大但片段数量可控的场景。在LeetCode本题的约束下0 clips[i][0] clips[i][1] 100 0 T 100方法一通常是更优的选择因为T很小预处理数组的开销可以忽略不计且整体时间复杂度是线性的。4. 关键细节与边界条件处理实现算法时细节决定成败。以下是几个极易出错的关键点片段起点的有效性在预处理方法中我们只处理start T的片段。因为如果某个片段的起点已经超过了目标T它对我们覆盖[0, T]毫无帮助可以直接忽略。这是一个重要的剪枝。maxEnd数组的初始化maxEnd[i]的初始值应该设为i而不是0。为什么假设没有任何片段以时间点5为起点那么maxEnd[5] 5表示从时间点5出发如果不借助任何片段最远只能走到5原地不动。这在后续判断“是否无法推进”时至关重要。在上面的代码中我们初始化maxEnd [0] * (T1)然后在遍历中通过max(curr_end, maxEnd[i])来更新由于curr_end在开始时是0所以效果等同于maxEnd[i]至少为i。更严谨的初始化应该是maxEnd list(range(T1))。循环终止条件在方法一的while循环中条件是i T。为什么不是i T因为我们的prev_end和curr_end维护的是已覆盖的右端点。当i遍历到T-1时我们仍然有机会通过maxEnd[T-1]来更新curr_end从而可能使得prev_end在循环内或循环结束后的判断中达到T。如果循环到i T此时maxEnd[T]通常就是T没有片段会从T开始这个判断是多余的。覆盖成功的判断标准最终判断成功的条件是prev_end T。注意是因为片段可能超过T例如一个片段是[5, 12]而T10这依然是有效的覆盖。T0的情况这是一个边界情况。如果目标时长T0那么不需要任何片段即可完成“覆盖”。我们的算法应该返回0。检查一下在方法一中如果T0maxEnd数组长度为1prev_end初始为0循环while i T根本不会进入最后判断prev_end (0) T (0)成立返回count (0)。正确处理。5. 实战问题排查与性能优化在实际编码或面试中你可能会遇到以下问题问题1算法返回-1但我觉得片段应该能拼出来。排查步骤检查预处理打印出maxEnd数组看每个起点对应的最远终点是否正确。常见错误是在更新maxEnd[start]时错误地写成了maxEnd[start] end而不是maxEnd[start] max(maxEnd[start], end)导致后出现的短片段覆盖了先出现的长片段信息。检查贪心循环逻辑核心在于if i prev_end:这个判断。在i追上prev_end的时刻curr_end必须大于i否则就说明断开了。可以在这个判断前后打印i,prev_end,curr_end的值观察它们的变化是否如预期。检查输入数据确认片段的时间是整数且满足0 start end。确认T是正整数。问题2算法返回的片段数比我认为的最小值要多。原因分析这通常是因为贪心策略在特定数据下看似“不贪心”了但其实是正确的。贪心保证的是全局最优而不是每一步都选最长的片段。例如片段为[[0,2],[2,4],[0,4]]T4。贪心算法在i0时curr_end通过maxEnd[0]更新为4然后在iprev_end(0)时选择这个[0,4]的片段count1prev_end4直接完成。结果是1个片段。如果你觉得应该选[0,2]和[2,4]那就是被局部迷惑了。贪心算法在第一步就看到了全局最优解。问题3当T很大时比如10^9方法一的maxEnd数组内存爆炸。优化方案此时应采用方法二排序贪心。或者可以对方法一进行改造使用哈希表字典来存储maxEnd映射只记录那些有片段起点的位置其他位置默认为自身。在遍历时如果i不在哈希表中则maxEnd[i] i。def videoStitching_large_T(clips, T): from collections import defaultdict maxEnd_map defaultdict(int) for s, e in clips: if s T: maxEnd_map[s] max(maxEnd_map[s], e) prev_end 0 curr_end 0 count 0 i 0 while i T: # 从哈希表获取如果没有则默认为i curr_end max(curr_end, maxEnd_map.get(i, i)) if i prev_end: if curr_end i: return -1 count 1 prev_end curr_end if prev_end T: break i 1 return count if prev_end T else -1问题4如何处理片段重叠非常多的情况性能影响无论是方法一还是方法二重叠多并不影响时间复杂度。方法一预处理是O(N)遍历是O(T)。方法二排序是O(N log N)遍历是O(N)。重叠多意味着maxEnd数组中的值较大或者在排序后的遍历中while循环内部会多比较几次但这些都是常数级别的操作不会改变算法的渐近复杂度。6. 从“视频拼接”到通用“区间覆盖”问题掌握“视频拼接”的解法你就掌握了一类问题的通解。我们可以将其抽象为一个模板问题模型给定一个目标区间[L, R]和一组子区间intervals求用最少的子区间完全覆盖[L, R]子区间可以重叠但不能有未被覆盖的缺口。贪心解法模板预处理计算每个“点”上通常是起点能向右延伸的最远距离。或者将子区间按起点排序。初始化设置covered_end L当前已覆盖的右端点next_max_end L下一轮能扩展到的最远点count 0。遍历在covered_end R的条件下寻找所有**起点小于等于covered_end**的子区间更新next_max_end为这些区间终点的最大值。选择与判断如果next_max_end covered_end则选择对应的区间计数1并令covered_end next_max_end。如果next_max_end covered_end说明无法再向前推进返回失败。返回结果循环结束后若covered_end R则返回count否则返回失败标识。这个模板可以应用到许多场景例如广播覆盖问题每个广播站有覆盖范围求用最少的站覆盖整个区域。任务调度每个任务有开始和结束时间求最少需要多少个机器或线程才能无间断执行所有任务稍作变形。跳跃游戏IILeetCode 45数组的每个元素代表你能跳的最远长度求到末尾的最少跳跃次数。这几乎是本题的一维翻版。我个人在解决这类问题时最深刻的体会是贪心算法的正确性严重依赖于问题本身的特性。在“视频拼接”中“选择当前可及范围内结束最晚的区间”之所以正确是因为我们的目标是覆盖一个固定区间且追求数量最少。在尝试使用贪心前必须花时间验证其正确性通常通过反证法或归纳法。一旦确认代码实现反而相对固定。多练习这类问题能极大地锻炼你的抽象建模能力和算法思维。下次再遇到“最少”、“覆盖”这类关键词不妨先想想能不能把它映射到这条时间线上。
