垫面没做出来

应该是greedy解法，方法和jump game 2一样，

这不是标准的区间覆盖问题嘛

将a转化为覆盖区间clips=[[-1,1], [0,2], [0,4], [2,4], [3,5]]，然就问题就变为如何选最少的区间来覆盖[0,4]. 和LC1024相同。
My solution

1.         int videoStitching(vector<vector<int>>& clips, int T)
   
2.     {
   
3.       sort(clips.begin(), clips.end()); // sort clips by start
   
4.       
   
5.       int i = 0; // clips index
   
6.       int maxReach = 0; // max time reachable by clips
   
7.       int cnt = 0; // number of clips needed
   
8.       
   
9.       while (maxReach < T) {
   
10.         int currentMaxReach = 0;
    
11.         while (i < clips.size() && clips[i][0] <= maxReach)
    
12.           currentMaxReach = max(currentMaxReach, clips[i++][1]);
    
13.         
    
14.         if (currentMaxReach <= maxReach) return -1; // can't reach further
    
15.         maxReach = currentMaxReach;
    
16.         cnt++; // need an additional clip to reach new maxReach        
    
17.       }
    
18.       
    
19.       return cnt;
    
20.     }

复制代码

[/i]

吃吃_ 发表于 2020/02/08 09:11:01
从[1,1,2,1,1]到[4,0,2,1,0]。从双向覆盖转换为单向覆盖。转换后的数组M=j代表从index=i的位置...

啊，谢谢大佬的讲解，我原本以为要用贪心法来做哩

henry_ma 发表于 2020/02/08 16:08:08
啊，谢谢大佬的讲解，我原本以为要用贪心法来做哩

这就是贪心呀

补充内容 (2020-2-8 01:03):
看错了，贪心比dp快

henry_ma 发表于 2020/02/08 16:08:08
啊，谢谢大佬的讲解，我原本以为要用贪心法来做哩

不是大佬...不客气哈哈哈哈，既然你懂了，还请你帮忙给我加个米呀～新人想多求点米看面经...

zzgzzm 发表于 2020-2-8 14:09
将a转化为覆盖区间clips=[[-1,1], [0,2], [0,4], [2,4], [3,5]]，然就问题就变为如何选最少的区间来覆盖[0, ...

LC1024的最优解也是O（nlogn） 吧？

浇花问题，Twitter今年的oa题，贪心可以做，好像也是上个月某次周赛的6分第四题

dionwang 发表于 2020-2-7 18:25
不是很像，就是

这1300多的题号，这是最近周赛的题？

WarriorZ 发表于 2020-2-8 12:05
浇花问题，Twitter今年的oa题，贪心可以做，好像也是上个月某次周赛的6分第四题

题号看着像周赛，hard题，前面三道是e m m，破案了