LeetCode 1024题保姆级攻略：用Python搞定视频拼接，快速排序+贪心算法实战解析

LeetCode 1024题保姆级攻略：用Python搞定视频拼接，快速排序+贪心算法实战解析

最近在刷LeetCode时遇到一道很有意思的题目——1024.视频拼接。这道题乍看简单，实则暗藏玄机，需要巧妙结合快速排序和贪心算法才能高效解决。作为算法爱好者，我花了整整一个周末研究这道题，现在把完整解题思路和Python实现分享给大家。

1. 理解题目本质

题目描述看似是关于视频剪辑，实则是一个典型的区间覆盖问题。我们需要从给定的视频片段中选择最少数量的片段，通过剪辑和拼接，完整覆盖从0到time的整个时间段。

举个例子：

• 输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
• 输出：3
• 解释：选择[0,2], [8,10], [1,9]三个片段，将[1,9]剪辑为[1,2]+[2,8]+[8,9]，最终得到[0,2]+[2,8]+[8,10]覆盖[0,10]

关键点在于：

1. 片段可以自由剪辑（即可以只使用片段的一部分）
2. 需要覆盖完整的[0, time]区间
3. 目标是使用最少数量的片段

2. 解题思路拆解

2.1 为什么需要快速排序？

原始片段是无序的，这会导致我们无法系统地遍历和选择片段。排序的目的是让所有片段按照起始时间升序排列，这样我们才能从左到右依次处理。

排序后的片段示例：

[[0,2],[1,9],[1,5],[4,6],[5,9],[8,10]]

2.2 贪心算法的核心思想

贪心算法在这里的应用是：在每一步选择能够最大限度扩展当前覆盖范围的片段。具体来说：

1. 维护两个关键变量：

   • current_end：当前已覆盖区间的右端点
   • next_end：下一步能覆盖的最大右端点

2. 遍历排序后的片段：

   • 如果片段的起始时间 ≤current_end，说明它可以扩展当前覆盖范围
   • 在这些片段中，选择能最大化next_end的片段
   • 当无法继续扩展时，选择next_end作为新的current_end，并增加片段计数

3. Python代码实现

def videoStitching(clips, time): # 先按起始时间排序 clips.sort() res = 0 current_end, next_end = 0, 0 i = 0 n = len(clips) while current_end < time and i < n: # 在所有起始时间<=current_end的片段中，找最大的结束时间 while i < n and clips[i][0] <= current_end: next_end = max(next_end, clips[i][1]) i += 1 if current_end == next_end: # 无法继续扩展 return -1 current_end = next_end res += 1 return res if current_end >= time else -1

代码解析：

1. clips.sort()：快速排序（Python内置的Timsort）
2. current_end和next_end的维护是贪心算法的核心
3. 当无法继续扩展时（current_end == next_end）返回-1
4. 最终检查是否完全覆盖[0, time]

4. 关键变量维护示例

让我们通过示例1来理解变量如何变化：

初始状态：

clips = [[0,2],[1,9],[1,5],[4,6],[5,9],[8,10]] current_end = 0, next_end = 0, res = 0

第一轮：

• 处理[0,2],[1,9],[1,5]（起始时间≤0的只有[0,2]）
• next_end = max(0, 2) = 2
• current_end = 2, res = 1

第二轮：

• 处理[1,9],[1,5],[4,6]（起始时间≤2）
• next_end = max(2, 9,5,6) = 9
• current_end = 9, res = 2

第三轮：

• 处理[5,9],[8,10]（起始时间≤9）
• next_end = max(9, 9,10) = 10
• current_end = 10 ≥ time(10)，结束

最终结果：res = 3

5. 复杂度分析

• 时间复杂度：O(nlogn)，主要由排序决定
• 空间复杂度：O(1)，只使用了常数个额外变量

6. 边界情况处理

在实际编码中，有几个边界情况需要特别注意：

1. 起始时间必须包含0：

   • 如果所有片段的start都>0，直接返回-1
   • 可以在排序后检查第一个元素的start是否为0

2. 时间范围检查：

   • 最终current_end必须≥time
   • 否则返回-1

3. 空输入处理：

   • 如果clips为空且time>0，返回-1
   • time=0时，返回0（不需要任何片段）

修改后的健壮代码：

def videoStitching(clips, time): if time == 0: return 0 if not clips: return -1 clips.sort() if clips[0][0] != 0: return -1 res = 0 current_end, next_end = 0, 0 i = 0 n = len(clips) while current_end < time and i < n: while i < n and clips[i][0] <= current_end: next_end = max(next_end, clips[i][1]) i += 1 if current_end == next_end: return -1 current_end = next_end res += 1 return res if current_end >= time else -1

7. 测试用例验证

为了确保代码的正确性，我们需要设计多种测试用例：

1. 基本用例：

assert videoStitching([[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], 10) == 3

2. 无法覆盖的情况：

assert videoStitching([[0,1],[1,2]], 5) == -1

3. 需要精确匹配的情况：

assert videoStitching([[0,4],[4,8],[8,10]], 10) == 3

4. 边界情况：

assert videoStitching([], 10) == -1 assert videoStitching([[1,2]], 1) == -1 assert videoStitching([[0,0]], 0) == 0

5. 复杂用例：

clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]] assert videoStitching(clips, 9) == 3

8. 贪心算法的正确性证明

为什么这种贪心策略能得到最优解？我们可以从几个方面理解：

1. 局部最优导致全局最优：每次选择能最大限度扩展覆盖范围的片段，确保不会错过更优的选择。

2. 无后效性：当前的选择不会影响后续的选择，因为所有起始时间≤current_end的片段都被考虑过了。

3. 数学归纳法：

   • 基础情况：第一个片段必须从0开始，选择能覆盖最远的片段
   • 归纳步骤：假设前k步是最优的，那么第k+1步选择能最大化扩展的片段也必然最优

9. 与动态规划的比较

这道题也可以用动态规划解决，但贪心算法更高效：

贪心算法的优势在于不需要存储中间状态，特别适合这种区间覆盖问题。

10. 实际应用场景

虽然题目描述是视频拼接，但这种算法可以应用于：

1. 会议日程安排：选择最少的会议室覆盖所有会议
2. 广告投放：选择最少的广告时段覆盖目标时间段
3. 资源分配：用最少的资源块满足连续需求

11. 常见错误与调试技巧

在实现过程中，我遇到过几个典型的错误：

1. 排序错误：

   • 错误：只按start排序，没有考虑start相同时的情况
   • 修正：Python的sort()会按元组顺序比较，所以不需要特殊处理

2. 变量更新时机错误：

   • 错误：在while循环外更新next_end
   • 修正：必须在找到所有候选片段后再更新

3. 终止条件错误：

   • 错误：只检查i < n而忽略current_end >= time
   • 修正：需要同时满足两个条件

调试时可以打印关键变量：

print(f"i={i}, current={current_end}, next={next_end}, res={res}")

12. 算法优化空间

虽然当前解法已经很高效，但仍有优化可能：

1. 提前终止：

   • 当current_end >= time时可以立即返回
   • 当next_end >= time时可以提前计算剩余需要的片段数

2. 特殊输入处理：

   • 如果存在单个片段覆盖全部时间，直接返回1
   • 可以在排序后先检查是否有这样的片段

优化后的代码片段：

# 在排序后添加检查 if clips[0][0] == 0 and clips[0][1] >= time: return 1

13. 类似题目推荐

掌握了这道题后，可以尝试以下类似题目巩固贪心算法：

1. 452.用最少数量的箭引爆气球
2. 435.无重叠区间
3. 56.合并区间
4. 1326.灌溉花园的最少水龙头数目

这些题目都涉及区间处理和贪心选择，解题思路有相通之处。

14. 从这道题中学到的经验

1. 问题转化很重要：将实际问题抽象为算法问题是关键第一步
2. 排序是预处理利器：很多看似复杂的问题，排序后就会变得清晰
3. 贪心需要证明：不能凭直觉使用贪心，要理解其正确性
4. 变量命名要清晰：像current_end、next_end这样的命名大大提高了代码可读性

这道题花了我不少时间理解，但收获很大。区间类问题在面试中很常见，掌握这种解题模式对算法提升很有帮助。建议读者亲自实现一遍代码，用不同的测试用例验证，才能真正掌握其中的精妙之处。