# 1024. Video Stitching
###### tags: `Leetcode` `Medium` `Greedy` `Intervals`
Link: https://leetcode.com/problems/video-stitching/description/
## 思路
类似[0045. Jump Game II](https://hackmd.io/eBarqjRNTIOUYBMU64wLKg)
差别在于我们要先给这些clips排序
我们从第一个区间```[0,far]```开始考虑，将之后所有左端点位于```far```之前的clips都查看一遍（意味着与之前的区间有overlap），考察他们各自的右端点，取最大值得到能够推进到最远的位置```nextFar```。这对应增加一个clip的操作（这个clip的右端点就是```nextFar```）。然后更新```far=nextFar```，再重复之前的操作，直到抵达target。

特别注意，如果更新```nextFar```之后仍然等于```far```，就意味着没有其他clip与当前的区间能够overlap，应该及时返回-1，否则会死循环。
## Code

class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, (a,b)->(a[0]-b[0]));
        int ans = 0;
        int far = 0, nextFar = 0;
        for(int i=0; i<clips.length; i++){
            if(clips[i][0]>far){
                if(nextFar<clips[i][0]) return -1;
                far = nextFar;
                ans++;
            }
            nextFar = Math.max(nextFar, clips[i][1]);
            if(nextFar>=time) return ans+1;
        }
        return -1;
    }
}