视频拼接

视频拼接

https://leetcode-cn.com/problems/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
39
40
41
42
func videoStitching(clips [][]int, time int) int {
    sort.Slice(clips, func(i, j int) bool {
        if clips[i][0] == clips[j][0] {
            return clips[i][1] > clips[j][1]
        } else {
            return clips[i][0] < clips[j][0]
        }
    })

    n := len(clips)
    count := 0
    currEnd, nextEnd := 0, 0
    
    for i := 0; i < n && clips[i][0] <= currEnd; {
        for i < n && clips[i][0] <= currEnd {
            // 寻找区间起点在 currEnd 前、区间终点最大的区间作为下一个区间
            nextEnd = max(nextEnd, clips[i][1])
            i++
        }

        // 选择这个区间，更新 currEnd 为这个区间的终点
        count++
        currEnd = nextEnd

        // 如果终点已经到达视频终点了，则可以拼凑出完整视频
        if currEnd >= time {
            return count
        }
    }

    return -1
}

func max(values ...int) int {
    res := values[0]
    for _, v := range values {
        if v > res {
            res = v
        }
    }
    return res
}