Leetcode.1024 视频拼接

这篇具有很好参考价值的文章主要介绍了Leetcode.1024 视频拼接。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目链接

Leetcode.1024 视频拼接 rating : 1746

题目描述

你将会获得一系列视频片段,这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。

使用数组 clips描述所有的视频片段,其中 c l i p s [ i ] = [ s t a r t i , e n d i ] clips[i] = [start_i, end_i] clips[i]=[starti,endi] 表示:某个视频片段开始于 s t a r t i start_i starti 并于 e n d i end_i endi 结束。

甚至可以对这些片段自由地再剪辑:

  • 例如,片段 [ 0 , 7 ] [0, 7] [0,7]可以剪切成 [ 0 , 1 ] + [ 1 , 3 ] + [ 3 , 7 ] [0, 1] + [1, 3] + [3, 7] [0,1]+[1,3]+[3,7] 三部分。

我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段( [ 0 , t i m e ] [0, time] [0,time])。返回所需片段的最小数目,如果无法完成该任务,则返回 − 1 -1 1

示例 1:

输入:clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出:3
解释:
选中 [0,2], [8,10], [1,9] 这三个片段。
然后,按下面的方案重制比赛片段:
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在手上的片段为 [0,2] + [2,8] + [8,10],而这些覆盖了整场比赛 [0, 10]。

示例 2:

输入:clips = [[0,1],[1,2]], time = 5
输出:-1
解释:
无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。

示例 3:

输入:clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
输出:3
解释:
选取片段 [0,4], [4,7] 和 [6,9] 。

提示:
  • 1 ≤ c l i p s . l e n g t h ≤ 100 1 \leq clips.length \leq 100 1clips.length100
  • 0 ≤ s t a r t i ≤ e n d i ≤ 100 0 \leq start_i \leq end_i \leq 100 0startiendi100
  • 1 ≤ t i m e ≤ 100 1 \leq time \leq 100 1time100

解法:贪心

用一个 d i s t dist dist记录以 i为左端点的最远右端点,即 dist[i]

pre记录上一段被选择区间的结束位置,用 last不断更新最远的区间。当 当前位置 i == pre时,答案 ans加 1,pre更新为 last

i == last时,说明选择的区间无法抵达 time,返回 − 1 -1 1

时间复杂度: O ( n ) O(n) O(n)

C++代码:

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        vector<int> dist(time);

        for(auto &e:clips){
            int l = e[0] , r = e[1];
            if(l < time) dist[l] = max(dist[l],r);
        }

        int pre = 0,last = 0;
        int ans = 0;

        for(int i = 0;i < time;i++){
            last = max(last,dist[i]);
            if(i == last) return -1;
            if(i == pre){
                pre = last;
                ans++;
            }
        }

        return ans;
    }
};


Python代码:文章来源地址https://www.toymoban.com/news/detail-671373.html

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        dist = [0] * time
        
        last = ret = pre = 0
        for l, r in clips:
            if l < time:
                dist[l] = max(dist[l], r)
        
        for i in range(time):
            last = max(last, dist[i])
            if i == last:
                return -1
            if i == pre:
                ret += 1
                pre = last
        
        return ret

到了这里,关于Leetcode.1024 视频拼接的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法沉淀——贪心算法一(leetcode真题剖析)

    贪心算法(Greedy Algorithm)是一种基于贪心策略的优化算法,它通常用于求解最优化问题,每一步都选择当前状态下的最优解,以期望通过局部最优的选择最终达到全局最优。贪心算法的思想是在每一步都做出在当前状态下局部最优的选择,而不考虑未来可能造成的影响。 在

    2024年03月08日
    浏览(49)
  • 算法沉淀——贪心算法五(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/jump-game-ii/ 给定一个长度为 n 的 0 索引 整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的最小跳跃次

    2024年04月11日
    浏览(49)
  • 算法沉淀——贪心算法二(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 示

    2024年03月19日
    浏览(50)
  • 算法沉淀——贪心算法七(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/integer-replacement/ 给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2 替换 n 。 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 2^31 - 1 思路 这里我们

    2024年03月23日
    浏览(48)
  • 算法沉淀——贪心算法六(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/broken-calculator/ 在显示着数字 startValue 的坏计算器上,我们可以执行以下两种操作: **双倍(Double):**将显示屏上的数字乘 2; **递减(Decrement):**将显示屏上的数字减 1 。 给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操

    2024年04月11日
    浏览(43)
  • leetCode 376.摆动序列 贪心算法

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果存在的话)可能是正数或负数。 仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如,  [1, 7, 4, 9, 2, 5]  是一个  摆动序列  ,因为差值  (6, -3, 5, -7, 3)  是正负

    2024年02月07日
    浏览(38)
  • LeetCode-455-分发饼干-贪心算法

    题目描述: 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] = g[i],我们可以将这个饼干 j 分配

    2024年02月10日
    浏览(41)
  • 贪心算法基础及leetcode例题

    参考 本质: 找到每个阶段的局部最优,然后去推导得到全局最优 两个极端: 常识很难: 很多同学通过了贪心的题目,但都不知道自己用了贪心算法,因为贪心有时候就是常识性的推导,所以会认为本应该就这么做! 套路: 贪心没有套路,说白了就是常识性推导加上举反例

    2023年04月20日
    浏览(71)
  • LeetCode:455. 分发饼干——贪心算法

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 贪心算法是在每个阶段选取 局部 最优解,最终得到 全局最优解 的一种思想。贪心算法与动态规划的思路相似,但贪心算法要在每个阶段选择最优解,而这个最优解不一定是全局最优解

    2023年04月15日
    浏览(37)
  • 【LeetCode】134. 加油站 - 贪心算法

    134. 加油站 贪心思想: 因为本题用到了贪心算法所以先来了解一下「贪心算法」的问题需要满足的条件: 最优子结构:规模较大的问题的解由规模较小的子问题的解组成,规模较大的问题的解只由其中一个规模较小的子问题的解决定; 无后效性:后面阶段的求解不会修改前

    2024年02月12日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包