Ming
0%

LeetCode-1024

Posted on Edited on In

题目

结果

代码

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
class Solution {
    public int videoStitching(int[][] clips, int T) {
        // 初始化数组range，range[i]值为0~i都可达的情况下最远的距离，-1说明不可达
        int[] range = new int[T + 1];
        Arrays.fill(range, -1);
        for (int[] clip : clips) {
            if (clip[0] == 0) {
                range[0] = Math.max(range[0], clip[1]);
            }
        }

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

        // 所需片段数，初始化为1
        int count = 1;
        for (int i = 1; i < range.length; i++) {
            if (range[i - 1] >= i) { // 不用额外的片段
                range[i] = range[i - 1];
            } else { // 需要额外的片段
                for (int[] clip : clips) {
                    if (i > clip[0] && i <= clip[1]) { // 包含i的最大范围
                        range[i] = Math.max(range[i], clip[1]);
                    }
                }
                if (range[i] != -1) {
                    count++;
                } else { // 如果片段i不可达
                    return -1;
                }
            }
        }
        return range[T] == -1 ? -1 : count;
    }
}

有点dp，但好像又不是dp。

复杂度

时间复杂度：O（n²）

空间复杂度：O（n）