LeetCode日记— 1024. Video Stitching

发布于 2020-10-24  118 次阅读


碎碎念:看到今天每日一题的题号彩蛋我才想起来今天是10/24程序员节。不知道说什么好了,那就祝我自己节日快乐吧。(对了,今晚有国家德比,希望别在节日给我喂💩)

题目如下:

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 clips [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 [1,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.
 

还有一点似乎示例中没有体现出来,就是时间片的开始时间可能大于你的视频的持续时间T。

思路

方法一(动态规划):

我们可以使用一个dp数组,来存储当前遍历到的第i个节点的最小分段数。

同时,我们要对第i个节点,遍历每个clip,如果i在这个clip的范围内,我们则认为i节点在选取了这个clip的情况下的dp值为dp[clip[0]]+1,遍历所有clip后得到第i个位置的最小值。

最终返回的结果应该是dp[T].

代码如下:

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/video-stitching/solution/shi-pin-pin-jie-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二(贪心算法):

这题和我前两天做的那道分段的题有很像的地方,都是要求最小的分段数。主要的区别在于本题是从已有的区间内选择分段,因此可能出现不能解决返回-1的情况。

主体思路还是相似的,就是对于每个位置,最好的结果肯定是选择最右的边界,若一直遍历到了边界则说明当前段已经结束。

但是,我们需要注意,右边界是已经确定的,因此我们要先预处理,得到每个位置i的最右右边界。

同时,因为右边界已经确定,因此我们需要记录下来当前分段的开始点的右边界。

同时,我们还需要维护一个当前可见最大右边界,每轮更新这个右边界。若是遍历i到达了这个最大右边界,则说明到达开始点边界前,就已经到达当前可达最大右边界了。这种情况下是无法分出可以满足要求的段的,因此返回-1.

代码如下

class Solution {
    public int videoStitching(int[][] clips, int T) {
        int[] maxMargin = new int[T];
        for(int[] clip: clips){
            if(clip[0]<T)
            maxMargin[clip[0]] = Math.max(maxMargin[clip[0]],clip[1]);
        }
        int last = 0,res=0,preLast=0;
        for(int i =0 ;i<T;i++){
            last = Math.max(last,maxMargin[i]);
            if(last==i){
                // 以及走到前面所有节点的最大边界了,还没有,说明当前条件下无解
                return -1;
            }
            if(preLast==i){
                // 遍历到了上一段的last,更新last,分段数++
                res+=1;
                preLast = last;
            }
        }
        return res;
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)