1024.视频拼接

贪心算法

暴力遍历每一个起点，每次找区间能到达的最远点，下一次的起始点小于等于这次的终点，下一次的终点继续尽可能远，当下一次的终点大于等于T时退出循环，如果最后终点也没有大于等于T，则返回-1.

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        int res = 1;
        int slow = 0;
        int fast = 0;
        vector<bool>visited(clips.size(),false);
        sort(clips.begin(),clips.end());
        for(int i=0;i<clips.size();i++)
        {
            fast = 0;
            for(int j=0;j<clips.size();j++)
            {
                if(clips[j][0]<=slow && visited[j] == false)
                {
                    if(clips[j][1]>=T)
                    {
                        return res;
                    }
                    if(clips[j][1]>=fast)
                    {
                        fast = clips[j][1];
                        visited[j] = true;
                    }
                }
            }
            slow = fast; 
            res++;               
            
        }
        if(fast<T)return -1;
        return res;       

    }
};

动态规划

保存0到T每一个点所需要拼接的数组个数，声明dp[i]初始值为INT_MAX-1，暴力遍历数组，如果存在一个区间起点小于等于i且终点大于等于i，则dp[i]为min(dp[i],dp[这个区间起点]+1)，初始条件为dp[0] = 0.

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
       vector<int>dp(T+1,INT_MAX-1);
       dp[0] = 0;
       for(int i=0;i<=T;i++)
       {
           for(int j=0;j<clips.size();j++)
           {
               if(clips[j][0]<=i && clips[j][1]>=i)
               {
                   dp[i] = min(dp[i],dp[clips[j][0]]+1);
               }
           }
       }
       return dp[T]==INT_MAX-1 ? -1 : dp[T];       

    }
};