LeetCode 1024. Video Stitching

题目意思：给你一些列视频片段，这些视频片段来自于一段时长为T的体育赛事，这些片是chips[i]  表示 开始于chips[i][0] 结束于chips[i][1]  我们的要就是 剪辑出一段一段时间为T的视频所需要的最小的视频数目。

解题思路： 这是一道典型的贪心题目，要需要的剪辑的视频数目最小 即可理解为 开始的时间越早 结束的时间越晚，那么视频的跨度越长 所需要的视频数目就越少。 在处理这种问题前 我们一般将 区间段进行一个排序 ， 按照开始时间从小到大排序。然后我们从第一个开始时间找到最迟的结束时间（注意 如果最小的结束时间 > 0  这表示 0 到这个开始时间前这段视频缺失  即不能得到答案 返回-1），记录下这个最迟的结束时间 ，片段数目+1  然后重复上述步骤。 找到下一个开始时间在这个结束时间之前 或者等于这个结束时间 。 找到这个片段记录下最迟的结束时间。 一直重复。 如果  最大的结束时间 大于T 那么我们就找到了 。 如果所有的片段遍历结束还没找到 说明不能找到 返回-1

代码如下：

 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 cnt = 0;
		int curStart = 0;
		int curEnd = 0; 
		for(int i = 0; i < clips.length; )  {
			int curMax = curEnd;
			if(clips[i][0] > curEnd) {
				return -1;
			}
			while(i < clips.length &&  clips[i][0] <= curEnd) {
				curMax = Math.max(curMax, clips[i][1]);
				i ++;
			}
            cnt ++;
			if(curMax >= T) {
				return cnt;
			} 
			curEnd = curMax;
		}
		return -1;
    }

注： 限作者水平有限，有任何问题欢迎评论区留言或者私信。欢迎幸福的骚扰

最后

以上就是震动小蝴蝶为你收集整理的LeetCode 1024. Video Stitching的全部内容，希望文章能够帮你解决LeetCode 1024. Video Stitching所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。