Leetcode 1024. Video Stitching

 这道题可以用贪心算法。首先把input按起始端排序，对于在同一段起始点开始的clip，我们只取其中最晚结束的那个。比如下图，对于起始点小于A的结束点的所有clip，应该无脑选C。

A -----------------------

B        --------------------------

C                   --------------------------------------

D                ----------

时间复杂度 O(nlogn), n代表clip数组长度，主要时间是排序

空间复杂度 O(1)

class Solution {

public:

    int videoStitching(vector<vector<int>>& clips, int time) {

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

        int end=0;

        int nextEnd=0;

        int numClips=1;

       

        for(int i=0; i<clips.size();) {

            if(clips[i][0]>end) return -1;

            while(i<clips.size() && clips[i][0]<=end) {

                nextEnd = max(nextEnd, clips[i++][1]);

            }

            if(nextEnd>=time){

                return numClips;

            }

            numClips++;

            end = nextEnd;

        }

       

        return -1;

    }

};