Force buckle 1024 video splicing

1、1024. Video splicing

Source force deduction analysis ：1024 Try to solve the problem
Medium difficulty 261

You'll get a series of video clips , These fragments come from an item with a duration of time Sports events in seconds . These fragments may overlap , It may also be of different lengths .

Using arrays clips Describe all the video clips , among clips[i] = [starti, endi] Express ： A video clip starts at starti And in endi end .

You can even freely re edit these clips ：

• for example , fragment [0, 7] It can be cut into [0, 1] + [1, 3] + [3, 7] In the third part of .

We need to re edit these clips , And then the edited content is spliced into a segment covering the whole motion process （[0, time]）. Returns the minimum number of fragments required , If you can't do it , Then return to -1 .

Example 1：

 Input ：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
 Output ：3
 explain ：
 Choose  [0,2], [8,10], [1,9]  These three clips .
 then , Remake the game clips as follows ：
 take  [1,9]  Then edit it as  [1,2] + [2,8] + [8,9] .
 Now the clip in hand is  [0,2] + [2,8] + [8,10], And these cover the whole game  [0, 10].

Example 2：

 Input ：clips = [[0,1],[1,2]], time = 5
 Output ：-1
 explain ：
 You can't just  [0,1]  and  [1,2]  Cover  [0,5]  The whole process .

Example 3：

 Input ：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
 Output ：3
 explain ： 
 Select segment  [0,4], [4,7]  and  [6,9] .

Example 4：

 Input ：clips = [[0,4],[2,8]], time = 5
 Output ：2
 explain ：
 Be careful , You may record a video longer than the end of the game .

analysis

First sort all videos in ascending order according to the start time. If the start time is the same, then sort them in descending order according to the end time

In this way, we greedily choose every interval as long as possible

Code

class Solution {
    public int videoStitching(int[][] clips, int time) {
        if(time== 0) return 0;
        Arrays.sort(clips,(a,b)->{
            if(a[0]==b[0]){
                return a[1]-b[1];
            }
            return a[0]-b[0];
        });
        int count=0;
        int i=0,n=clips.length;
        int cur_end=0,next_end=0;
        while(i<n && clips[i][0]<=cur_end){
            while(i<n && clips[i][0]<=cur_end){
                next_end=Math.max(next_end,clips[i][1]);
                i++;
            }
            count++;
            cur_end=next_end;
            if(cur_end>=time) return count;
        }
    return -1;
    }
}