剪视频剪出一个贪心算法 :: labuladong的算法小抄

[labuladong]

文章链接点这里：剪视频剪出一个贪心算法

评论礼仪 见这里，违者直接拉黑。

[taoziganbei]

贪心策略就是：每次都选择能到达的最远的地方

[zhongweiLeex]

有关 更新curEnd的时机

记住 这里的停止条件 并不是找到了 一个end 比 curEnd还要大的，而是 当一个视频的开始时间 大于curEnd的时候才停止，但是不用担心，这里的i到n就停了，且 记录 合格的视频的 是 result 与 i无关 所以是隔离开来的

     while(i<n && clips[i][0]<=curEnd){//此位置
                nextEnd = Math.max(nextEnd,clips[i][1]);//i==0 的时候 第0条一定会被选择
                i++;
            }

[Alwin4Zhang]

这个算法原理跟图上的不一样啊，是怎么个工作机制啊？

[lzh2580]

@Alwin4Zhang 原理一样，只不过第一个片段得确定是从0开始的片段，如果没有的话不存在

[JuniorJason]

和跳跃游戏一样，只是这题要 保证 第一跳 从0开始，且是跳的最远的那个（所以要 按照start升序，end降序），后面逻辑一样，都是在每一跳范围内找 最远的下一跳。

[potatogit]

这道题不用排end的，只排start就好了。因为对end排序也不能保证优先选择到最合适的区间

[Maxiah]

这题好绕啊…………感觉这个应该是最接近跳跃游戏的那个代码了

class Solution {
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if(a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    }
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        // 二维跳跃游戏
        // 与其说是贪心更像是dp

        sort(clips.begin(),clips.end(),cmp);

        int curEnd = 0, farthest = 0; 
        // int result = 0;
        int result = 1; // 初始化为1是因为什么

        if(clips.size() == 0) return -1;

        for(int i = 0;i < clips.size(); i++){
            // [0,2],[1,9],[1,5],[4,6],[5,9],[8,10]
            // base case
            if(farthest >= time || farthest < clips[i][0]){
                break;
            }
            if(clips[i][0] > curEnd){
                // 如果当前左端大于curEnd
                curEnd = farthest; 
                cout << "cur:"<< curEnd << " ";
                result++;
            }
            farthest = max(farthest,clips[i][1]); // 2,9,10
            cout << "far:"<< farthest<< " ";
        }
        return farthest >= time ? result : -1;
    }
};

[mengbingrock]

官方题解的贪心没有排序，是O(time+n)的复杂度。没有这里的答案好理解。

[yonggui-yan]

打卡. 实现方式，两个while循环，很精干呀

[miiiiiko]

既然每次nextEnd都要比较取较大值，那就没有必要end按从大到小排序了，尝试直接clips.sort()也可以过，说明end的排序无关紧要

[EyeDroplyq]

打卡，附上详细注解的Java代码

    public int videoStitching(int[][] clips, int time) {
        //区间调度问题再加最值问题，所以使用贪心算法，排序规则是按照开始时间进行一个升序排列，如果开始时间相同再按照结束时间降序排列，
        //因为我们开始时间相同的话，我们肯定优先选择长的那个片段，这样需要的数量就会少点
        if(time==0){
            return 0;
        }
        Arrays.sort(clips,((o1, o2) -> {
            if(o1[0]==o2[0]){
                //开始时间相同的话，降序排列
                return o2[1]-o1[1];
            }else{
                //如果开始时间不同，按照开始时间进行升序排列
                return o1[0]-o2[0];
            }
        }));
        //记录最后需要几个视频片段
        int res=0;
        //当前的结束时间
        int curEndTime=0;
        //下一次的结束时间
        int nextEndTime=0;
        int n=clips.length;
        int i=0;
        //其实我们的循环条件是从排序后的第一个片段开始遍历，一直找到视频片段开始时间大于当前结束时间的片段就结束
        while (i<n && clips[i][0]<=curEndTime){
            while (i<n && clips[i][0]<=curEndTime){
                //下一次的结束时间就是开始时间小于等于当前结束时间的片段中，结束时间最晚的那个
                nextEndTime=Math.max(nextEndTime,clips[i][1]);
                i++;
            }
            //只要while循环能进来就选中了一个片段，所以res就要加1
            res++;
            curEndTime=nextEndTime;
            if (curEndTime>=time){
                return res;
            }
        }
        //如果while循环没进去，说明没有片段开始时间是0的，所以返回-1
        return -1;
    }

[gaosh96]

这个问题可以泛化成给定 [x,y] 区间中的一些小区间，计算最小能组成整个区间的小区间个数。

需要理解两个地方

1. curEnd 的初始值为多少？

// 这个值要取排序后的起点位置，也就是 x，这样才能让第一个区间也进入比较
// nextEnd 的初始值为 x 或者排序后第一个区间的 end 值都可以
int curEnd = x,nextEnd = x;

2. 两个 while 循环代表什么？

// 当前区间能否和当前最大 end 的区间连续起来
while (i < n && clips[i][0] <= curEnd) {
	// 可以连续起来，找到最大的那个 end 区间
	// 对于第一轮，也就是找到了起点最大的那个 end 的区间
	// 对于后面的比较，找到在 curEnd 范围中最大的那个 end 的区间
	while (i < n && clips[i][0] <= curEnd) {