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

ゝ一世哀愁。 2022-12-18 00:55 203阅读 0赞

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

![leet][]

该题目的链接: [https://leetcode-cn.com/problems/video-stitching/][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;
        }

[leet]: /images/20221122/47fdfdd433d646c78eb43cbe48d73d3a.png
[https_leetcode-cn.com_problems_video-stitching]: https://leetcode-cn.com/problems/video-stitching/