LeetCode1024. Video Stitching

1、题目链接

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

2、解题思路

这道题的意思是给你一些视频片段，每一个视频片段包括一个起始时间和一个结束时间[start, end]，都存储在一个二维数组中，然后让你从这些视频片段中找出能够完整拼接时间长度为T的一个视频，要求用到的片段最少；看起来又是一道贪心类的题，和我们之前做过的一道Jump Game跳跃游戏也有相似之处的，要想完整，且还要用到的片段最少，首先视频必须从0开始，否则就不完整了，那么数组中最小的start值就必须是0，所以我们需要对数组进行一个排序操作，然后如果需要用到的片段最少，那么每次选取的片段的end必须最大（在符合条件的情况下）；

示例 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]。

拿一个示例来看，上面排好序之后就是[[0, 2], [1, 9], [1, 5], [4, 6], [5, 9], [8, 10]]，我们初始一个当前片段是[0, 0]，然后遍历整个数组，找到end比当前片段end要大的，并且他的start要比当前的end小，要不然就拼接不上，每次遍历一次都会找到一个最大的片段来和上一次的拼接，如果没有找到，说明拼接不上，那么此时就直接返回-1。

3、代码

public int videoStitching(int[][] clips, int T) {
    if (null == clips || clips.length == 0) {
        return -1;
    }
    // 排序
    Arrays.sort(clips, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] - o2[0];
        }
    });
    if (clips[0][0] != 0) {
        return -1;
    }
    int len = clips.length;
    int maxEnd = 0;   //记录每次找到的最长片段的end值，下一次要找的片段需要 start <= maxEnd && maxEnd < end
    int count = 0;
    int curIndex = 0;   //防止重复遍历之前用过的片段
    while (maxEnd < T) {
        int end = 0;
        for (int i = curIndex; i < len; i++) {
            if (clips[i][0] <= maxEnd && clips[i][1] > maxEnd) {
                end = Math.max(end, clips[i][1]);
                curIndex = i;
            }
        }
        if (end == 0) {  //说明该次查找拼接不上上一次的片段，直接返回-1
            return -1;
        }
        count++;
        maxEnd = end;
    }
    return count;
}

4、结果

1563350193298.jpg