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

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

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

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

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...