Leetcode-5019 Video Stitching(视频拼接)

 1 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 2 class Solution
 3 {
 4     public:
 5         int videoStitching(vector<vector<int>>& clips, int T)
 6         {
 7             int judge[T+1];
 8             memset(judge,0,sizeof(judge));
 9             _for(i,0,clips.size())
10                 _for(j,clips[i][0],min(T+1,clips[i][1]+1))
11                     judge[j] ++;
12 
13             _for(i,0,T+1)
14                 if(judge[i]==0)
15                     return -1;
16                     
17             sort(clips.begin(),clips.end());
18     
19             int mark = 0;
20             int rnt = 0;
21             int index = 0;
22             int tmpmark = -1;
23             while(mark<T && index < clips.size())
24             {
25                 if(clips[index][0]<=mark)
26                 {
27                     tmpmark = max(tmpmark,clips[index][1]);
28                     index ++;
29                 }
30                 else
31                 {
32                     mark = tmpmark;
33                     rnt ++;
34                 }
35             }
36             if(mark<T)
37                 return rnt+1;
38             return rnt;
39         }
40 };
排序贪心