LeetCode 1024 - Video Stitching

https://leetcode.com/problems/video-stitching/

You are given a series of video clips from a sporting event that lasted T seconds.  These video clips can be overlapping with each other and have varied lengths.

Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1].  We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]).  If the task is impossible, return -1.

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation: 
We take the clcips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation: 
We can't cover [0,5] with only [0,1] and [0,2].

Example 3:

Input: 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]], T = 9
Output: 3
Explanation: 
We can take clips [0,4], [4,7], and [6,9].

Example 4:

Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation: 
Notice you can have extra video after the event ends.

Note:

1. 1 <= clips.length <= 100
2. 0 <= clips[i][0], clips[i][1] <= 100
3. 0 <= T <= 100

X. Greedy
https://blog.csdn.net/fuxuemingzhu/article/details/89074761

这个题还是很容易想到贪心的。贪心策略是在保证和前面的区间能连接的情况下，选择结尾最靠后的区间，这样的覆盖是最广的。举例来说，如果现在的区间是[0,3]，假设下一个区间要从[1,5]和[2,4]中选择，我们应该选择结尾最靠后的也就是[1,5]。

对于每个相同开头结尾的区间，我只保留结尾最大的那个。这个策略是相同开头的时候，覆盖越大越好。这样，总的区间数目不会超过100个。

然后，我看了Note里的提示，发现时间段的取值范围只有100，所以使用了一个暴力的方法：遍历。即对于区间[a,b]暴力遍历a+1到b中的每个元素，找出是否以该元素开头的区间：如果有，那么找出所有区间最靠后的结尾，则该区间是下一个应该选择的区间。如果对a+1和b之间的所有元素都遍历了，然而找不到存在的区间，那么一定断线了，所以返回-1.

这种贪心策略之下，则选取的区间个数是最少的。

https://xingxingpark.com/Leetcode-1024-Video-Stitching/

先对clips按起始段位置从小到大排序。然后我们用贪心算法，用cur_end记录当前实际位置的最远端，potential_end记录目前可能的最远端。分别初始化为-1和0。

对clips进行遍历：

1. 当potential_end大于T或者clip的起始位置大于potential_end，意味着之后所有的clip都不需要再做考虑了，要么已经满足题意，要么就会出现不能覆盖的区间。
2. 否则，当clip的起始位置大于cur_end，意味着为了覆盖所有区间，必须更新cur_end 和 potential_end，同时有一个clip需要加入res中。

(贪心算法) $O(nlogn)$

1.将每一个区间按照左端点递增顺序排列，如果左端点相同，按右端点递增顺序排列；
2.设置两个变量last和far。last表示当前已经覆盖到的区域的最右边距离，far表示在剩下的线段中找到的所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，不断更新最右边的距离；
3.重复以上过程 直到区间全部覆盖 否则区间不能全部覆盖。
4.贪心证明：要求用最少的线段进行覆盖，那么选取的线段必然要尽量长，而已覆盖到的区域之前的地方已经不用考虑了，可以理解成所有可覆盖的左端点都已被覆盖了，那么能够使得线段更长的取决于右端点，左端点没有太大的意义，所以选择右端点来覆盖。

时间复杂度分析：排序需要$O(nlogn)$时间，贪心需要$O(n)$时间，总时间复杂度为$O(nlogn)$。

http://www.noteanddata.com/leetcode-5019-Video-Stitching-java-solution-note.html

1. 首先可以对clips按照开始时间排序， 然后对于第一个，一定需要找一个开始时间是0的，否则就不能符合要求；
   然后，对于开始时间都是0的，一定是需要找end最大的才最划算；
2. 找到一个curend以后， 那么就在所有start<= curend里面找， 这时候同样也可以用贪心的思想，在这些里面选择end最大的最划算；
3. 循环直到找到curend>=T

https://leetcode.com/problems/video-stitching/discuss/269984/java-O(N*lgN)-greedy

      public int videoStitching(int[][] clips, int T) {
          Arrays.sort(clips, new Comparator<int[]>() {
              public int compare(int[] a, int[] b) {
                  return a[0]-b[0];
              }
          });    
          int count = 0;
          int curend = 0;
          int laststart = -1;
          
          for(int i = 0; i < clips.length; ) {
              if(clips[i][0] > curend) {
                  return -1;
              }
              int maxend = curend;
              while(i < clips.length && clips[i][0] <= curend) { // while one clip's start is before or equal to current end
                  maxend = Math.max(maxend, clips[i][1]); // find out the one with the max possible end
                  i++;
              }
              count++;
              curend = maxend;
              if(curend >= T) {
                  return count;    
              }
          }
          return -1;        
      }

https://leetcode.com/problems/video-stitching/discuss/269988/C%2B%2BJava-6-lines-O(n-log-n)

We track our current stitching position (st). For each iteration, we check all overlapping clips, and pick the one that advances our stitching position the furthest.

Solution

We sort our clips by the starting point. Since clips are sorted, we need to only analyze each clip once. For each round, we check all overlapping clips (clips[i][0] <= st) and advance our stitching position as far as we can (end = max(end, clips[i][1])).

Return -1 if we cannot advance our stitching position (st == end).

public int videoStitching(int[][] clips, int T) {
  int res = 0;
  Arrays.sort(clips, new Comparator<int[]>() {
    public int compare(int[] a, int[] b) { return a[0] - b[0]; }
  });
  for (int i = 0, st = 0, end = 0; st < T; st = end, ++res) {
    for (; i < clips.length && clips[i][0] <= st; ++i)
      end = Math.max(end, clips[i][1]);
    if (st == end) return -1;
  }
  return res;
}

Complexity Analysis

Runtime: O(n log n), where n is the number of clips. We sort all clips, and then processing each clip only once.

X. https://leetcode.com/problems/video-stitching/discuss/270350/Java-DP-Short-Solution-!!!

    public int videoStitching(int[][] clips, int T) {
        int[] dp = new int[T+ 1];
        Arrays.fill(dp, T+1);
        dp[0] = 0;
        for(int i = 0; i <= T; i++) {
            for(int[] c : clips) {
                if(i >= c[0] && i <= c[1]) dp[i] = Math.min(dp[i], dp[c[0]] + 1);
            }
            if(dp[i] == T+1) return -1;
        }
        return dp[T];
    }

X. DP
https://leetcode.com/problems/video-stitching/discuss/270036/JavaC%2B%2BPython-Greedy-Solution-O(1)-Space

Sort

Time O(NlogN), Space O(1)

    public int videoStitching(int[][] clips, int T) {
        int res = 0;
        Arrays.sort(clips, (a,b) ->  a[0] - b[0]);
        for (int i = 0, st = 0, end = 0; st < T; st = end, ++res) {
            for (; i < clips.length && clips[i][0] <= st; ++i)
                end = Math.max(end, clips[i][1]);
            if (st == end) return -1;
        }
        return res;
    }

Solution 2: Sort + DP

Sort clips first.
Then for each clip, update dp[clip[0]] ~ dp[clip[1]].

Time O(NlogN + NT), Space O(T)

C++

    int videoStitching(vector<vector<int>>& clips, int T) {
        sort(clips.begin(), clips.end());
        vector<int> dp(101, 101);
        dp[0] = 0;
        for (auto& c : clips)
            for (int i = c[0] + 1; i <= c[1]; i++)
                dp[i] = min(dp[i], dp[c[0]] + 1);
        return dp[T] >= 100 ? -1 : dp[T];
    }

Solution 3: DP

Loop on i form 0 to T,
loop on all clips,
If clip[0] <= i <= clip[1], we update dp[i]

Time O(NT), Space O(T)

    public int videoStitching(int[][] clips, int T) {
        int[] dp = new int[T + 1];
        Arrays.fill(dp, T + 1);
        dp[0] = 0;
        for (int i = 0; i <= T && dp[i - 1] < T; i++) {
            for (int[] c : clips) {
                if (c[0] <= i && i <= c[1])
                    dp[i] = Math.min(dp[i], dp[c[0]] + 1);
            }
        }
        return dp[T] == T + 1 ? T + 1 : dp[T];
    }

https://www.acwing.com/solution/LeetCode/content/1745/

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

样例

示例 1：

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
输出：3
解释：
我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。
示例 2：

输入：clips = [[0,1],[1,2]], T = 5
输出：-1
解释：
我们无法只用 [0,1] 和 [0,2] 覆盖 [0,5] 的整个过程。
示例 3：

输入：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]], T = 9
输出：3
解释： 
我们选取片段 [0,4], [4,7] 和 [6,9] 。
示例 4：

输入：clips = [[0,4],[2,8]], T = 5
输出：2
解释：
注意，你可能录制超过比赛结束时间的视频。




X. Video

花花酱 LeetCode 1024. Video Stitching - 刷题找工作 EP248