LeetCode 1024：视频拼接（贪心）

74 阅读 0 评论 49 点赞

我是靠谱客的博主调皮篮球，最近开发中收集的这篇文章主要介绍LeetCode 1024：视频拼接（贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接

题目：
在这里插入图片描述

方法一：贪心

思路：
先按照起点升序排序，如果起点相同的话按照终点降序排序，主要考虑到这道题的以下两个特点：

要用若干短视频凑出完成视频 [0, T]，起点必须是 0 ！
如果有几个短视频的起点都相同，那么⼀定应该选择那个最长（curEnd终点最⼤）的视频。

在这里插入图片描述
排好序以后，首先第一个区间的Start必须 >= 0，即起点一定从0开始！

然后以当前区间为基准，while遍历所有 Start 在curEnd内的区间，选出End最大的区间的nextEnd，作为下一次的基准！
用count记录所有基准的个数；

直到 curEnd > time ，就可以结束了，返回count即可；若跳出while即不满足time，就返回-1；

class Solution {
    public int videoStitching(int[][] clips, int time) {
    // 排序： start 顺排， end逆排
    Arrays.sort(clips,new Comparator<int[]>(){
        public int compare(int[] a,int[] b){
            if(a[0]==b[0]){
                return b[1]-a[1];
            }
            return a[0]-b[0];
        }
    });
    //
    int n=clips.length;
    int curEnd=0;
    int nextEnd=0;
    int count=0;
    int i=0;     // 一定要从0 开始 ！
// 区间必须要重叠或者接触，若 clips[i][0] >curEnd则有空隙！
    while(i<n && clips[i][0]<=curEnd){
        // 以第 i个为基准,贪心选择end最大的作为下一个cur
        while(i<n && clips[i][0] <=curEnd ){
            // 贪心选择nextEnd最大
            nextEnd=Math.max(nextEnd,clips[i][1]);
            i++;
        }
        count++;
        // 更新基准,currSart可以省去
        curEnd=nextEnd;    
        if(curEnd>=time){
            return count;
        }
    }
    // 无法拼出 time
    return -1;
    }
}