LeetCode 1024：视频拼接（贪心）

比眉伴天荒 2024-04-07 13:43 52阅读 0赞

[链接][Link 1]

**题目**：  
![在这里插入图片描述][c52b4d41d01f43378b9635de54e4e86a.png]

### 方法一：贪心 ###

**思路**：  
先按照**起点升序排序**，**如果起点相同的话按照终点降序排序**，主要考虑到这道题的以下 两个特点：

1.  要用若干短视频凑出完成视频 \[0, T\]，**起点必须是 0 ！**
2.  如果有几个短视频的起点都相同，那么⼀定应该选择那个最长（**curEnd终点最⼤**）的视频。

![在这里插入图片描述][1a1293b6515b4cc6868aa9dccbddc52d.png]  
排好序以后，首先第一个区间的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;
        }
    }

[Link 1]: https://leetcode.cn/problems/video-stitching/
[c52b4d41d01f43378b9635de54e4e86a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/0db22794e13b4ab78b500125726c017a.png
[1a1293b6515b4cc6868aa9dccbddc52d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b13371ac600d455f9a7d9c4b57249840.png