1024. Video Stitching 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, (o1, o2) -> {
            // 先按起点排序，起点相同的按终点倒序，以使左侧的区间尽量长
            int diff = Integer.compare(o1[0], o2[0]);
            if (diff != 0) {
                return diff;
            }
            return Integer.compare(o2[1], o1[1]);
        });

        if (clips[0][0] != 0) {
            return -1;
        }

        int end = 0;
        int i = 0;
        int count = 0;

        while (i < clips.length && clips[i][0] <= end) {
            // 下一个区间左边界小于等于当前区间右边界，说明两区间有交集，可能可以延长
            int nextEnd = end;
            while (i < clips.length && clips[i][0] <= end) {
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++;
            }

            end = nextEnd;
            count++;

            if (end >= time) {
                return count;
            }
        }

        return -1;
    }
}

References

1024. Video Stitching