当前位置: 首页 > news >正文

Leetcode.1024 视频拼接

题目链接

Leetcode.1024 视频拼接 Rating : 1746

题目描述

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

使用数组 clips描述所有的视频片段,其中 clips[i] = [starti, endi]表示:某个视频片段开始于 starti并于 endi结束。

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

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

我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, time])。返回所需片段的最小数目,如果无法完成该任务,则返回 -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<=clips.length<=1001 <= clips.length <= 1001<=clips.length<=100
  • 0<=starti<=endi<=1000 <= starti <= endi <= 1000<=starti<=endi<=100
  • 1<=time<=1001 <= time <= 1001<=time<=100

解法:贪心

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

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

i == last时,说明选择的区间无法抵达 time,返回 -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代码:

class Solution:def videoStitching(self, clips: List[List[int]], time: int) -> int:dist = [0] * timelast = ret = pre = 0for 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 -1if i == pre:ret += 1pre = lastreturn ret

相关文章:

Leetcode.1024 视频拼接

题目链接 Leetcode.1024 视频拼接 Rating &#xff1a; 1746 题目描述 你将会获得一系列视频片段&#xff0c;这些片段来自于一项持续时长为 time秒的体育赛事。这些片段可能有所重叠&#xff0c;也可能长度不一。 使用数组 clips描述所有的视频片段&#xff0c;其中 clips[i…...

20个华为路由器常用的Python脚本,网工写自动化脚本时候可以参考!

你好&#xff0c;这里是网络技术联盟站。 昨天给大家介绍了10个华为交换机的Python脚本&#xff1a; 10个华为华为交换机常用的Python脚本&#xff0c;网络工程师收藏&#xff01; 大家反响不错&#xff0c;后期我会陆续出一下思科、H3C、锐捷等厂商的脚本&#xff0c;前期会…...

【kubernetes云原生】k8s资源管理命令与Namespace使用详解

目录 一、前言 二、k8s概述 三、k8s常用操作管理命令 3.1 kubectl 命令用法 3.2 常用控制台管理命令演示 3.2.1 获取全部节点信息 3.2.2 获取当前集群下全部pod 3.2.3 查看某个pod信息 3.2.4 获取当前集群下的所有namespace信息 3.2.5 查看当前集群下已创建的资源 3…...

String源码深度刨析

前言 我们将从源码角度深度分析特点&#xff0c;来提升对他们的了解以及设计。 String、StringBuilder、StringBuffer的常见面试题及四大区别可以参考&#xff1a;String、StringBuilder、StringBuffer的四大区别解析 String public final class Stringimplements java.io.Se…...

FreeRTOS - 消息队列

一.消息队列的概念及应用消息队列&#xff08;queue&#xff09;&#xff1a;可以在任务与任务间、中断和任务间传递消息&#xff0c;实现任务接收来自其他任务或中断的不固定的消息1.1任务需求1、使用消息队列检测串口输入2、通过串口发送字符串openled1&#xff0c;openled2&…...

怎样正确做 Web 应用的压力测试?

环境 首先环境是非常重要的&#xff0c;需要尽可能跟生产环境靠近。 比方说&#xff0c;使用同样的nginx版本&#xff0c;php的话需要启用fpm&#xff0c;zend-optimizer等等&#xff0c;参数配置也最好跟生产环境保持一致。 当然&#xff0c;php的版本更加需要保持一致&#x…...

php mysql大学生求职招聘资源信息网zkfdzkf67a8

1&#xff0e;系统登录&#xff1a;系统登录是用户访问系统的路口&#xff0c;设计了系统登录界面&#xff0c;包括用户名、密码和验证码&#xff0c;然后对登录进来的用户判断身份信息&#xff0c;判断是管理员用户还是普通用户。 2&#xff0e;系统用户管理&#xff1a;不管是…...

2023上海市“星光计划”职业院校技能大赛 网络安全竞赛试题任务书

2023上海市“星光计划”职业院校技能大赛 网络安全竞赛试题任务书 A模块基础设施设置/安全加固&#xff08;200分&#xff09; 一、项目和任务描述&#xff1a; 假定你是某企业的网络安全工程师&#xff0c;对于企业的服务器系统&#xff0c;根据任务要求确保各服务正常运行&…...

Spring事务源码:创建代理类

参考文章&#xff1a; 《Spring事务源码解析之tx:annotation-driven标签解析》 《Spring 源码解析—事务执行》 参考资料&#xff1a; 《Spring AOP源码&#xff1a;开启注解读取》 《Spring AOP源码2&#xff1a;查找增强器》 《Spring AOP源码3&#xff1a;实现代理》 …...

java14 使用增强的模式匹配切换表达式

野旷天低树&#xff0c;江清月近人。——唐代杜甫《月夜忆舍弟》 使用增强的模式匹配切换表达式(Switch Expressions with Enhanced Pattern Matching) Java 14中引入的“Switch Expressions with Enhanced Pattern Matching”这个功能。 这个功能可以让我们在使用switch cas…...

python【正则表达式】

正则表达式 1.正则的作用 正则表达式式一种可以让复杂的字符串变得简单的工具。 写正则表达式的时候就是用正则符号来描述字符串规则。 2.正则语法 需要导入模块 from re import fullmatch, findall, search2.1.第一类&#xff1a;匹配类符号 1&#xff09;普通字符—在…...

Ubuntu常见系统问题解决方式

Ubuntu常见系统问题解决方式Ubuntu每次开机后提示检测到系统程序出现问题的解决方法Ubuntu循环登陆问题问题描述原因解决方法文件夹打开缓慢Ubuntu启动后GUI界面卡住不动Ubuntu18.04使用过程中常遇到的问题Ubuntu每次开机后提示检测到系统程序出现问题的解决方法 首先&#xf…...

C/C++中的虚拟内存

文章目录一、虚拟内存二、C中的虚拟内存分配模型三、C中的虚拟内存分配模型四、堆区和栈区的区别一、虚拟内存 虚拟内存是一种实现在计算机软硬件之间的内存管理技术&#xff0c;它将程序使用到的内存地址&#xff08;虚拟地址&#xff09;映射到计算机内存中的物理地址&#…...

Qt C++与Python混合编程:补充错误

在提示中&#xff0c;需要引用Python.h&#xff0c;出现错误。 1、找不到Python.h 如果是pro工程&#xff0c;需要在里面配置&#xff1b; INCLUDEPATH /Users/xinnianwang/opt/anaconda3/include LIBS /Users/xinnianwang/opt/anaconda3/lib 如果是CMakeLists.txt需要配…...

2023-04-01:当Go语言遇见FFmpeg视频解码器,使用Go语言改写decode_video.c文件,提升视频解码效率与开发体验。

2023-04-01&#xff1a;当Go语言遇见FFmpeg视频解码器&#xff0c;使用Go语言改写decode_video.c文件&#xff0c;提升视频解码效率与开发体验。 答案2023-04-01&#xff1a; 步骤如下&#xff1a; 1.导入必要的依赖库&#xff0c;包括 fmt、os、unsafe 和其它 FFmpeg 库相关…...

Solidity 学习笔记

主要参考网上资料学习&#xff0c;个人学习笔记有删改&#xff0c;参考出处在文末列出。 0 基础 IDE: remixType Bool: bool public _bool true; 默认false;整型&#xff1a;int、uint、uint256&#xff0c;默认0;地址类型&#xff1a;address&#xff0c;分为 payable 和普…...

ThreadLocal原理

关键点总结&#xff1a; ThreadLocal更像是对其他类型变量的一层包装&#xff0c;通过ThreadLocal的包装使得该变量可以在线程之间隔离和当前线程全局共享。在Thread中有一个threadLocals变量&#xff0c;类型为ThreadLocal.ThreadLocalMap&#xff0c;ThreadLocalMap中key是Th…...

串操作指令详解 MOVS,LODS,STOS,CMPS,SCAS,REP

指令包括&#xff1a;MOVS&#xff0c;LODS&#xff0c;STOS&#xff0c;CMPS&#xff0c;SCAS&#xff0c;REP 串的概念&#xff1a;串是连续存放再内存中的字节块或字块。每个串有一个起始地址和长度&#xff0c; 待操作的数据串称为源串&#xff0c;目的地址称为目标串 目录…...

Java实现判断素数

1 问题 判断101-200之间有多少个素数&#xff0c;并输出所有素数。 2 方法 package homework04; public class Test05 { public static void main(String[] args) { for (int i 101; i < 201; i) { boolean flag true; for (int j 2; j…...

PHP初级教程------------------(2)

目录 运算符 赋值运算符 算术运算符 比较运算符 逻辑运算符 连接运算符 错误抑制符 三目运算符 自操作运算符 ​编辑 计算机码 位运算符 运算符优先级 流程控制 控制分类 顺序结构 分支结构 If分支 ​ Switch分支 循环结构 For循环 while循环 do-while循环 循环控制 ​ …...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...