LeetCode 1024 视频拼接：快速排序与贪心算法的完美结合
面对LeetCode上这道看似简单实则暗藏玄机的视频拼接问题，许多开发者第一次接触时都会感到无从下手。这道编号1024的题目要求我们将一系列可能重叠的视频片段拼接成完整的赛事录像，不仅考察对基础算法的掌握程度，更考验将实际问题转化为算法模型的能力。本文将带你深入剖析这道经典题目，从问题理解到算法选择，再到代码实现，一步步拆解其中的精妙之处。
1. 问题本质与难点分析
视频拼接问题初看似乎只是一个简单的区间覆盖问题，但深入分析后会发现几个关键难点：
- 片段重叠与剪裁：原始片段可以自由剪裁，这意味着我们不需要完全匹配区间，只要能够覆盖整个时间范围即可。这种灵活性增加了问题复杂度。
- 最小片段数要求：我们需要找到能够覆盖整个时间段的最少片段组合，这直接指向了贪心算法的适用场景。
- 边界条件处理：如何判断无法完成拼接？如何处理片段的起始和结束时间？这些细节决定了算法的鲁棒性。
示例分析： 以题目中的第一个示例为例：
输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10最优解是选择[0,2]、[1,9]和[8,10]三个片段，通过剪裁[1,9]为[1,2]+[2,8]+[8,9]，最终组合成[0,2]+[2,8]+[8,10]的完整覆盖。
2. 算法选择：为何快速排序+贪心是最佳组合
2.1 快速排序的必要性
在处理区间问题时，排序往往是第一步。快速排序因其平均O(nlogn)的时间复杂度成为首选：
- 排序标准：我们需要按照片段的开始时间升序排列，这样可以从左到右线性扫描。
- 相同开始时间的处理：当开始时间相同时，应选择结束时间更长的片段，这能减少后续需要的片段数量。
void quickSort(int** clips, int low, int high) { if (low < high) { int pivot = partition(clips, low, high); quickSort(clips, low, pivot - 1); quickSort(clips, pivot + 1, high); } } int partition(int** clips, int low, int high) { int pivot = clips[high][0]; int i = low - 1; for (int j = low; j < high; j++) { if (clips[j][0] < pivot || (clips[j][0] == pivot && clips[j][1] > clips[high][1])) { i++; swap(&clips[i][0], &clips[j][0]); swap(&clips[i][1], &clips[j][1]); } } swap(&clips[i+1][0], &clips[high][0]); swap(&clips[i+1][1], &clips[high][1]); return i + 1; }2.2 贪心算法的实现策略
贪心算法在此问题中的核心思想是：每一步都选择能够覆盖当前时间点且延伸最远的片段。
实现步骤：
- 初始化当前覆盖范围为0，计数器为0
- 在已排序的片段中，找到所有开始时间≤当前覆盖范围的片段
- 从这些片段中选择结束时间最大的一个
- 更新当前覆盖范围，增加计数器
- 重复直到覆盖整个时间段或无法继续
3. 完整代码实现与逐行解析
下面给出完整的C语言实现，并附上详细注释：
#include <stdio.h> // 快速排序实现 void quickSort(int** clips, int low, int high) { if (low < high) { int pivot = clips[low][0]; int i = low, j = high; int tempStart, tempEnd; while (i < j) { while (i < j && clips[j][0] >= pivot) j--; if (i < j) { tempStart = clips[i][0]; tempEnd = clips[i][1]; clips[i][0] = clips[j][0]; clips[i][1] = clips[j][1]; clips[j][0] = tempStart; clips[j][1] = tempEnd; i++; } while (i < j && clips[i][0] <= pivot) i++; if (i < j) { tempStart = clips[j][0]; tempEnd = clips[j][1]; clips[j][0] = clips[i][0]; clips[j][1] = clips[i][1]; clips[i][0] = tempStart; clips[i][1] = tempEnd; j--; } } quickSort(clips, low, i - 1); quickSort(clips, i + 1, high); } } int videoStitching(int** clips, int clipsSize, int* clipsColSize, int time) { // 第一步：对片段按照开始时间排序 quickSort(clips, 0, clipsSize - 1); int currentEnd = 0; // 当前已覆盖的时间终点 int result = 0; // 使用的片段计数 int i = 0; while (currentEnd < time) { int maxEnd = currentEnd; // 找出所有开始时间<=currentEnd的片段中结束时间最大的 while (i < clipsSize && clips[i][0] <= currentEnd) { if (clips[i][1] > maxEnd) { maxEnd = clips[i][1]; } i++; } // 如果没有找到可以扩展的片段，说明无法完成 if (maxEnd == currentEnd) { return -1; } // 更新当前终点并增加计数 currentEnd = maxEnd; result++; // 如果已经覆盖了整个时间段，直接返回 if (currentEnd >= time) { return result; } } return -1; }4. 常见错误与调试技巧
在实际实现过程中，开发者常会遇到以下几个典型问题：
排序规则不正确：
- 仅按开始时间排序而忽略相同开始时间时的结束时间
- 解决方案：当开始时间相同时，选择结束时间更长的片段
边界条件处理不足：
- 未检查第一个片段是否从0开始
- 未正确处理无法覆盖的情况
- 解决方案：初始化currentEnd为0，并在无法扩展时立即返回-1
贪心策略实现错误：
- 没有每次选择能覆盖当前终点且延伸最远的片段
- 解决方案：在内层循环中跟踪maxEnd
调试建议：
- 使用小规模测试用例验证边界条件
- 打印排序后的片段顺序检查排序是否正确
- 在每次选择片段后打印当前覆盖范围
5. 算法复杂度与优化空间
5.1 时间复杂度分析
| 步骤 | 时间复杂度 | 说明 |
|---|---|---|
| 快速排序 | O(nlogn) | 平均情况下的时间复杂度 |
| 贪心扫描 | O(n) | 线性扫描已排序的数组 |
| 总计 | O(nlogn) | 主要由排序步骤决定 |
5.2 可能的优化方向
排序优化：
- 对于小规模数据，可改用插入排序
- 考虑使用更稳定的排序算法如归并排序
贪心策略优化：
- 预处理时记录每个时间点对应的最大结束时间
- 这样可以避免排序，时间复杂度可降至O(n+time)
空间优化：
- 如果允许修改输入数组，可以实现原地排序
- 使用更紧凑的数据结构存储片段信息
6. 实际应用与变种问题
视频拼接问题不仅仅是一道算法题，它在实际中有广泛的应用场景：
- 视频编辑软件：自动拼接不同镜头
- 网络流媒体：组合不同质量的视频片段
- 监控系统：整合多个摄像头的录像
变种问题：
- 加权区间覆盖：每个片段有不同的权重，求最小总权重的覆盖
- 多资源覆盖：需要同时覆盖多个时间线（如视频和音频）
- 最大覆盖问题：给定固定数量的片段，求能覆盖的最大时间范围
7. 从这道题中学到的算法思维
解决LeetCode 1024的过程完美展示了算法设计的典型思路：
- 问题抽象：将实际问题转化为区间覆盖模型
- 预处理：通过排序使数据更有结构性
- 分步解决：使用贪心算法逐步构建解决方案
- 边界处理：全面考虑各种异常情况
这种先排序再贪心的模式可以应用到许多类似问题中，如：
- 区间合并问题
- 会议室安排问题
- 任务调度问题
掌握这种解题范式，能够帮助开发者快速识别和解决一大类区间相关问题。
