1024节，程序员不准不“贪心”-记录 LeetCode 1024 节每日一题_leetcode 1024 贪心 图解

今天是1024 程序员节，今天 LeetCode 的每日一题也淘气的选择了 1024

该题目的链接: https://leetcode-cn.com/problems/video-stitching/

参照官方的贪心解题思想:

    public int videoStitching(int[][] clips, int T) {
        if (clips == null) {
            return 0;
        }
        
        // 定义一个数组来存储可能用到的视频片段
        int[] array = new int[T];
        // 数组的下标表示视频片段的开始时间
        // 数组的值表示视频片段的结束时间
        // 如果有多个视频片段的开始时间相同，那么值就取结束时间最大的那个

        // 初始化数组
        for (int[] clip : clips) {
            if (clip[0] < T) {
                // 值取结束时间最大的那个
                array[clip[0]] = Math.max(array[clip[0]], clip[1]);
            }
        }

        // 所需片段的最小数目(方法返回结果)
        int minCount = 0;
        // 记录每一个片段的结束位置
        int end = 0;
        // 记录上一个片段的可达的最大位置
        int curEnd = 0;
        for (int i = 0; i < T; i++) {
            end = Math.max(end, array[i]);
            // 下一个位置无法被覆盖(也就无法达到最大位置)
            if (i == end) {
                return -1;
            }
            if (curEnd == i) {
                minCount++;
                curEnd = end;
            }
        }
        return minCount;
    }

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