题目：
方法一：贪心
思路：
先按照起点升序排序，如果起点相同的话按照终点降序排序，主要考虑到这道题的以下 两个特点：
- 要用若干短视频凑出完成视频 [0, T]，起点必须是 0 ！
- 如果有几个短视频的起点都相同，那么⼀定应该选择那个最长（curEnd终点最⼤）的视频。
排好序以后，首先第一个区间的Start必须 >= 0，即起点一定从0开始！
然后以当前区间为基准，while遍历所有 Start 在curEnd内的区间，选出End最大的区间的nextEnd，作为下一次的基准！
用count记录所有基准的个数；
直到 curEnd > time ，就可以结束了，返回count即可；若跳出while即不满足time，就返回-1；
class Solution {
public int videoStitching(int[][] clips, int time) {
// 排序： start 顺排， end逆排
Arrays.sort(clips,new Comparator<int[]>(){
public int compare(int[] a,int[] b){
if(a[0]==b[0]){
return b[1]-a[1];
}
return a[0]-b[0];
}
});
//
int n=clips.length;
int curEnd=0;
int nextEnd=0;
int count=0;
int i=0; // 一定要从0 开始 ！
// 区间必须要重叠或者接触，若 clips[i][0] >curEnd则有空隙！
while(i<n && clips[i][0]<=curEnd){
// 以第 i个为基准,贪心选择end最大的作为下一个cur
while(i<n && clips[i][0] <=curEnd ){
// 贪心选择nextEnd最大
nextEnd=Math.max(nextEnd,clips[i][1]);
i++;
}
count++;
// 更新基准,currSart可以省去
curEnd=nextEnd;
if(curEnd>=time){
return count;
}
}
// 无法拼出 time
return -1;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89180.html
