1. 项目概述：从“视频拼接”到“区间覆盖”的算法思维跃迁

第一次看到“视频拼接”这个标题，你可能会下意识地想到视频编辑软件里的时间轴，拖动、裁剪、合并片段。但在算法世界里，LeetCode第1024题“视频拼接”却是一个披着生活外衣的经典算法问题。它不关心视频编码格式，也不处理像素数据，它的核心是区间覆盖。想象一下，你手头有一堆长短不一的视频片段（每个片段有确定的开始和结束时间），你的目标是用最少的片段，无缝拼接出一段从0时刻到目标时间T的完整视频。这本质上就是在一条时间线上，用给定的区间（视频片段）去覆盖一个更大的目标区间[0, T]。

这个问题之所以经典且被选入LeetCode，是因为它完美地将一个实际场景抽象成了一个可被计算机高效求解的模型。它考察的是对贪心算法的深刻理解，以及对区间类问题的预处理和遍历技巧。无论是准备技术面试，还是希望提升解决实际规划类问题的能力，吃透这道题都能让你获益匪浅。它适合所有正在学习算法与数据结构，尤其是对贪心策略和区间问题感到困惑的开发者。接下来，我将带你深入拆解这道题，从问题本质、思路推导、代码实现到避坑指南，完整走一遍。

2. 核心思路拆解：为什么贪心策略是正解？

面对“视频拼接”，一个最朴素的想法可能是回溯或动态规划：尝试所有片段的组合，看哪个组合能覆盖[0, T]且用的片段最少。这在片段数量少时可行，但一旦数据量增大，时间复杂度将呈指数级爆炸。我们必须寻找更优解。

仔细分析问题特性，我们可以发现两个关键点，这直接指向了贪心算法：

1. 目标区间是固定的：我们要覆盖的是从0到T的连续区间，起点是0。
2. 我们关心的是“最远能延伸到哪”：在选择片段时，对于一个已经覆盖到的位置i，我们希望在所有起点小于等于i的片段中，选择一个结束时间最晚的片段。因为结束时间越晚，它一次性覆盖的范围就越大，就越有可能用更少的片段到达T。

这引出了解决此问题的核心贪心策略：我们维护一个当前覆盖到的最远位置last。在每一轮中，我们遍历所有起点小于等于last的片段，从中选出结束时间最大的那个，用它来更新last（相当于将这段视频拼接到时间线上），同时增加片段计数。重复这个过程，直到last达到或超过T，或者无法再找到可以扩展last的片段。

注意：这里有一个至关重要的预处理步骤。为了能高效地找到“起点小于等于last的片段中结束时间最晚的”，我们通常不直接遍历clips数组。一个更聪明的做法是，预处理一个数组maxEnd[i]，表示所有以时间点i为起点的片段中，最大的结束时间是多少。如果没有任何片段以i为起点，则maxEnd[i] = i（即无法延伸）。这个预处理能将每次寻找“最远可到达位置”的操作降到O(1)复杂度。

为什么贪心在这里能保证最优解？我们可以用反证法简单理解：假设在某一步，我们根据贪心策略选择了一个结束时间为E1的片段A，而存在另一个结束时间为E2（E2 > E1）的片段B可选但我们没选。那么，选择A之后我们到达的位置是E1，后续我们需要更多的片段才能从E1走到T。而如果当初选择了B，我们直接就到了E2（E2 > 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数组 # 数组长度为 T+1 就足够了，因为超过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

代码逐行解析：

1. 预处理 (maxEnd数组)：maxEnd[i]存储了所有以i为起点的片段中，最大的结束时间。例如，片段[0,2]和[0,4]都会影响maxEnd[0]，最终maxEnd[0] = 4。
2. 三个核心变量：
   • prev_end：可以理解为“当前已拼好的视频的结束时间点”。在贪心选择中，当我们决定使用一个新片段时，prev_end会更新为这个新片段的结束时间。
   • curr_end：在遍历过程中，它动态维护着“从当前位置i及之前的所有位置出发，能到达的最远位置”。它通过maxEnd[i]不断更新。
   • count：记录使用的片段数。
3. 贪心选择时机：当遍历的指针i追上prev_end时（i == prev_end），说明上一段视频已经播放完了，我们必须开始选择一个新的片段来接上。此时，curr_end的值就代表了所有“起点在prev_end及之前”的片段中，能带我们去到的最远地方。我们选择这个能带我们去curr_end的片段（虽然代码中没有显式记录是哪个片段，但这个动作在逻辑上发生了）。
4. 无法覆盖的判断：如果在i == prev_end时，发现curr_end <= i，意味着没有哪个片段的起点小于等于i且结束时间大于i，时间线在这里断掉了，无法完成拼接，返回-1。

3.2 方法二：排序 + 贪心

另一种思路是先将片段按起点升序，终点降序排序，然后进行一轮贪心遍历。这种方法更直观地体现了“在可选的片段里选结束最晚的”这一过程。

def videoStitching(clips, T): # 1. 排序：先按起点升序，起点相同的按终点降序 clips.sort(key=lambda 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

两种方法对比：

在LeetCode本题的约束下（0 <= clips[i][0] < clips[i][1] <= 100， 0 < T <= 100），方法一通常是更优的选择，因为T很小，预处理数组的开销可以忽略不计，且整体时间复杂度是线性的。

4. 关键细节与边界条件处理

实现算法时，细节决定成败。以下是几个极易出错的关键点：

1. 片段起点的有效性：在预处理方法中，我们只处理start <= T的片段。因为如果某个片段的起点已经超过了目标T，它对我们覆盖[0, T]毫无帮助，可以直接忽略。这是一个重要的剪枝。

2. maxEnd数组的初始化：maxEnd[i]的初始值应该设为i，而不是0。为什么？假设没有任何片段以时间点5为起点，那么maxEnd[5] = 5，表示从时间点5出发，如果不借助任何片段，最远只能走到5（原地不动）。这在后续判断“是否无法推进”时至关重要。在上面的代码中，我们初始化maxEnd = [0] * (T+1)，然后在遍历中通过max(curr_end, maxEnd[i])来更新，由于curr_end在开始时是0，所以效果等同于maxEnd[i]至少为i。更严谨的初始化应该是maxEnd = list(range(T+1))。

3. 循环终止条件：在方法一的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开始），这个判断是多余的。

4. 覆盖成功的判断标准：最终判断成功的条件是prev_end >= T。注意是>=，因为片段可能超过T（例如一个片段是[5, 12]，而T=10），这依然是有效的覆盖。

5. T=0的情况：这是一个边界情况。如果目标时长T=0，那么不需要任何片段即可完成“覆盖”。我们的算法应该返回0。检查一下，在方法一中，如果T=0，maxEnd数组长度为1，prev_end初始为0，循环while i < T根本不会进入，最后判断prev_end (0) >= T (0)成立，返回count (0)。正确处理。

5. 实战问题排查与性能优化

在实际编码或面试中，你可能会遇到以下问题：

问题1：算法返回-1，但我觉得片段应该能拼出来。

• 排查步骤：
  1. 检查预处理：打印出maxEnd数组，看每个起点对应的最远终点是否正确。常见错误是在更新maxEnd[start]时，错误地写成了maxEnd[start] = end而不是maxEnd[start] = max(maxEnd[start], end)，导致后出现的短片段覆盖了先出现的长片段信息。
  2. 检查贪心循环逻辑：核心在于if i == prev_end:这个判断。在i追上prev_end的时刻，curr_end必须大于i，否则就说明断开了。可以在这个判断前后打印i,prev_end,curr_end的值，观察它们的变化是否如预期。
  3. 检查输入数据：确认片段的时间是整数，且满足0 <= start < end。确认T是正整数。

问题2：算法返回的片段数比我认为的最小值要多。

• 原因分析：这通常是因为贪心策略在特定数据下看似“不贪心”了，但其实是正确的。贪心保证的是全局最优，而不是每一步都选最长的片段。例如，片段为[[0,2],[2,4],[0,4]]，T=4。贪心算法在i=0时，curr_end通过maxEnd[0]更新为4，然后在i==prev_end(0)时，选择这个[0,4]的片段，count=1，prev_end=4，直接完成。结果是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]，子区间可以重叠，但不能有未被覆盖的缺口。

贪心解法模板：

1. 预处理：计算每个“点”上（通常是起点）能向右延伸的最远距离。或者，将子区间按起点排序。
2. 初始化：设置covered_end = L（当前已覆盖的右端点），next_max_end = L（下一轮能扩展到的最远点），count = 0。
3. 遍历：在covered_end < R的条件下，寻找所有**起点小于等于covered_end**的子区间，更新next_max_end为这些区间终点的最大值。
4. 选择与判断：如果next_max_end > covered_end，则选择对应的区间（计数+1），并令covered_end = next_max_end。如果next_max_end == covered_end，说明无法再向前推进，返回失败。
5. 返回结果：循环结束后，若covered_end >= R则返回count，否则返回失败标识。

这个模板可以应用到许多场景，例如：

• 广播覆盖问题：每个广播站有覆盖范围，求用最少的站覆盖整个区域。
• 任务调度：每个任务有开始和结束时间，求最少需要多少个机器（或线程）才能无间断执行所有任务（稍作变形）。
• 跳跃游戏II（LeetCode 45）：数组的每个元素代表你能跳的最远长度，求到末尾的最少跳跃次数。这几乎是本题的一维翻版。

我个人在解决这类问题时，最深刻的体会是：贪心算法的正确性严重依赖于问题本身的特性。在“视频拼接”中，“选择当前可及范围内结束最晚的区间”之所以正确，是因为我们的目标是覆盖一个固定区间，且追求数量最少。在尝试使用贪心前，必须花时间验证其正确性（通常通过反证法或归纳法）。一旦确认，代码实现反而相对固定。多练习这类问题，能极大地锻炼你的抽象建模能力和算法思维。下次再遇到“最少”、“覆盖”这类关键词，不妨先想想能不能把它映射到这条时间线上。