欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

视频拼接(区间预处理,贪心)

程序员文章站 2022-03-11 14:51:19
Leetcode 每日一题题目链接: 1024. 视频拼接解题思路: 将给定的区间进行预处理,获得每个左端点对应的最大的有端点。在整个区间上进行遍历,每次动态更新能达到的最大长度,对每个区间进行覆盖,若某个区间全部被覆盖,则区间数量+1。题解:class Solution: def videoStitching(self, clips: List[List[int]], T: int) -> int: # 以左端点开头的最大右端点 ma...

Leetcode 每日一题
题目链接: 1024. 视频拼接
解题思路: 将给定的区间进行预处理,获得每个左端点对应的最大的有端点。在整个区间上进行遍历,每次动态更新能达到的最大长度,对每个区间进行覆盖,若某个区间全部被覆盖,则区间数量+1。
题解:

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        
        # 以左端点开头的最大右端点
        max_index = [0 for i in range(T + 1)]

        for example in clips:
            # print(example)
            if example[0] <= T:
                max_index[example[0]] = max(max_index[example[0]], example[1])
        
        # cnt记录片段数量, pre记录前一个找到的右端点位置,last表示当前的最大右端点
        cnt, pre, last = 0, 0, 0
        for t in range(T):
            last = max(max_index[t], last)

            # 有空缺, 不能完全覆盖。 由于t < T所以不用担心最后一个元素
            if t == last:
                return -1

            # 匹配到前一个的结尾,覆盖了整个区间,可以找新的区间了    
            if t == pre:
                cnt += 1
                pre = last
        
        return cnt
        
            

本文地址:https://blog.csdn.net/qq_37753409/article/details/109258321