当前位置: 首页 > 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循环 循环控制 ​ …...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...