剪视频时，每个视频片段都可以抽象成了一个个区间，时间就是区间的端点，这些区间有的相交，有的不相交……

假设剪辑软件不支持将视频片段还原成原视频，那么如果给我若干视频片段，我怎么将它们还原成原视频呢？

这是个很有意思的区间算法问题，也是力扣第 1024 题「视频拼接」，题目如下：

视频拼接区间算法问题 - 图1

函数签名如下：

  1. int videoStitching(int[][] clips, int T);

算上本文的区间剪辑问题，经典的区间问题也就都讲完了。

思路分析

题目并不难理解，给定一个目标区间和若干小区间，如何通过裁剪和组合小区间拼凑出目标区间？最少需要几个小区间？

前文多次说过，区间问题肯定按照区间的起点或者终点进行排序。

因为排序之后更容易找到相邻区间之间的联系，如果是求最值的问题，可以使用贪心算法进行求解。

至于到底如何排序，这个就要因题而异了，我做这道题的思路是先按照起点升序排序，如果起点相同的话按照终点降序排序。

为什么这样排序呢，主要考虑到这道题的以下两个特点：

1、要用若干短视频凑出完成视频[0, T]，至少得有一个短视频的起点是 0。

这个很好理解，如果没有一个短视频是从 0 开始的，那么区间[0, T]肯定是凑不出来的。

2、如果有几个短视频的起点都相同，那么一定应该选择那个最长（终点最大）的视频。

这一条就是贪心的策略，因为题目让我们计算最少需要的短视频个数，如果起点相同，那肯定是越长越好，不要白不要，多出来了大不了剪辑掉嘛。

基于以上两个特点，将clips按照起点升序排序，起点相同的按照终点降序排序，最后得到的区间顺序就像这样：

视频拼接区间算法问题 - 图2

这样我们就可以确定，如果clips[0]是的起点是 0，那么clips[0]这个视频一定会被选择。

视频拼接区间算法问题 - 图3

当我们确定clips[0]一定会被选择之后，就可以选出第二个会被选择的视频：

视频拼接区间算法问题 - 图4

我们会比较所有起点小于**clips[0][1]**的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频。

然后可以通过第二个视频区间贪心选择出第三个视频，以此类推，直到覆盖区间[0, T]，或者无法覆盖返回 -1。

以上就是这道题的解题思路，仔细想想，这题的核心和前文 贪心算法玩跳跃游戏 写的跳跃游戏是相同的，如果你能看出这两者的联系，就可以说理解贪心算法的奥义了。

代码实现

实现上述思路需要我们用两个变量curEnd和nextEnd来进行：

视频拼接区间算法问题 - 图5

最终代码实现如下：

  1. int videoStitching(int[][] clips, int T) {
  2.     if (T == 0) return 0;
  3.     // 按起点升序排列，起点相同的降序排列
  4.     Arrays.sort(clips, (a, b) -> {
  5.         if (a[0] == b[0]) {
  6.             return b[1] - a[1];
  7.         }
  8.         return a[0] - b[0];
  9.     });
  10.     // 记录选择的短视频个数
  11.     int res = 0;
  13.     int curEnd = 0, nextEnd = 0;
  14.     int i = 0, n = clips.length;
  15.     while (i < n && clips[i][0] <= curEnd) {
  16.         // 在第 res 个视频的区间内贪心选择下一个视频
  17.         while (i < n && clips[i][0] <= curEnd) {
  18.             nextEnd = Math.max(nextEnd, clips[i][1]);
  19.             i++;
  20.         }
  21.         // 找到下一个视频，更新 curEnd
  22.         res++;
  23.         curEnd = nextEnd;
  24.         if (curEnd >= T) {
  25.             // 已经可以拼出区间 [0, T]
  26.             return res;
  27.         }
  28.     }
  29.     // 无法连续拼出区间 [0, T]
  30.     return -1;
  31. }

c++版

  1.  if (time == 0) return 0;
  2.        // 按起点升序排列，起点相同的降序排列
  3.     sort(clips.begin(),clips.end(),[](vector<int> a, vector<int> b){
  4.         if (a[0] == b[0]) {
  5.             return a[1] > b[1];
  6.         }
  7.         return a[0] < b[0];
  8.     });
  9.     // 记录选择的短视频个数
  10.     int res = 0;
  11.     int curEnd = 0, nextEnd = 0;
  12.     size_t i = 0;
  13.     size_t n = clips.size();
  14.     while (i < n && clips[i][0] <= curEnd) {
  15.         // 在第 res 个视频的区间内贪心选择下一个视频
  16.         while (i < n && clips[i][0] <= curEnd) {
  17.             nextEnd = max(nextEnd, clips[i][1]);
  18.                i++;
  19.         }
  20.         // 找到下一个视频，更新 curEnd
  21.         res++;
  22.         curEnd = nextEnd;
  23.         if (curEnd >= time) {
  24.             // 已经可以拼出区间 [0, T]
  25.             return res;
  26.         }
  27.     }
  28.        // 无法连续拼出区间 [0, T]
  29.        return -1;

这段代码的时间复杂度是多少呢？虽然代码中有一个嵌套的 while 循环，但这个嵌套 while 循环的时间复杂度是O(N)。因为当i递增到n时循环就会结束，所以这段代码只会执行O(N)次。

但是别忘了我们对clips数组进行了一次排序，消耗了O(NlogN)的时间，所以本算法的总时间复杂度是O(NlogN)。