【C++ 动态规划】1024. 视频拼接|1746

本文涉及知识点

C++动态规划

LeetCode1024. 视频拼接

你将会获得一系列视频片段,这些片段来自于一项持续时长为 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 <= 100
0 <= starti <= endi <= 100
1 <= time <= 100

动态规划

注意:本题是左闭右开空间,包括starti,不包括endi。
N = 100
end[i] 表示以i开始的片段,最大结束时间;-1,表示不存在。 空间复杂度:O(n)

动态规划的状态表示

dp[i]表示包括前i秒需要的最少片段数。

动态规划的填表顺序

i = 0 to N

动态规划的转移方程

∀ \forall i
j = i to end[i]
MinSelf(dp[j+1],dp[i]+1)
时间复杂度:O(nn)

动态规划的初始化

dp[0]=0 其它全为INT_MAX/2。

动态规划的返回值

dp.back()

代码

核心代码

class Solution {public:int videoStitching(vector<vector<int>>& clips, int time) {vector<int> end(101, -1);for (const auto& v : clips) {end[v[0]] = max(end[v[0]], v[1]-1);}vector<int> dp(102,INT_MAX/2);dp[0] = 0;for (int i = 0; i <= 100; i++) {for (int j = i; j <= end[i]; j++) {dp[j + 1] = min(dp[j + 1], dp[i] + 1);}}return (dp[time] > time+1) ? -1: dp[time];}};

单元测试

	vector<vector<int>> clips;int time;TEST_METHOD(TestMethod11){clips = { {0,2},{4,6},{8,10},{1,9},{1,5},{5,9} }, time = 10;auto res = Solution().videoStitching(clips,time);AssertEx(3, res);}TEST_METHOD(TestMethod12){clips = { {0,1},{1,2} }, time = 5;auto res = Solution().videoStitching(clips, time);AssertEx(-1, res);}TEST_METHOD(TestMethod13){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;auto res = Solution().videoStitching(clips, time);AssertEx(3, res);}TEST_METHOD(TestMethod14){clips = { {0,5},{6,8} }, time = 7;auto res = Solution().videoStitching(clips, time);AssertEx(-1, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/8301.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

可扩展架构:如何打造一个善变的柔性系统?

系统的构成:模块 + 关系 我们天天和系统打交道,但你有没想过系统到底是什么?在我看来,系统内部是有明确结构 的,它可以简化表达为: 系统 = 模块 + 关系 在这里,模块是系统的基本组成部分,它泛指子系统、应用、服务或功能模块。关系指模块 之间的依赖关系,简单…

TOGAF之架构标准规范-信息系统架构 | 数据架构

TOGAF是工业级的企业架构标准规范&#xff0c;信息系统架构阶段是由数据架构阶段以及应用架构阶段构成&#xff0c;本文主要描述信息系统架构阶段中的数据架构阶段。 如上所示&#xff0c;信息系统架构&#xff08;Information Systems Architectures&#xff09;在TOGAF标准规…

【OMCI实践】ONT上线过程的omci消息(二)

引言 在上一篇文章【OMCI实践】ONT上线过程的omci消息&#xff08;一&#xff09;-CSDN博客&#xff0c;主要介绍了ONT上线过程的OMCI交互的四个阶段&#xff0c;本篇开始介绍上线过程的omci消息&#xff0c;重点介绍涉及到的受管实体&#xff08;ME&#xff09;的属性。 OMC…

C++ STL:深入探索常见容器

你好呀&#xff0c;欢迎来到 Dong雨 的技术小栈 &#x1f331; 在这里&#xff0c;我们一同探索代码的奥秘&#xff0c;感受技术的魅力 ✨。 &#x1f449; 我的小世界&#xff1a;Dong雨 &#x1f4cc; 分享我的学习旅程 &#x1f6e0;️ 提供贴心的实用工具 &#x1f4a1; 记…

ShenNiusModularity项目源码学习(7:数据库结构)

ShenNiusModularity项目默认使用mysql数据库&#xff0c;数据库连接字符串放到了ShenNius.Admin. Mvc、ShenNius.Admin.Hosting的appsettings.json文件内。   ShenNiusModularity项目为自媒体内容管理系统&#xff0c;支持常规管理、CMS管理、商城管理等功能&#xff0c;其数…

论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(五)

Understanding Diffusion Models: A Unified Perspective&#xff08;五&#xff09; 文章概括基于得分的生成模型&#xff08;Score-based Generative Models&#xff09; 文章概括 引用&#xff1a; article{luo2022understanding,title{Understanding diffusion models: A…

服务器上安装Nginx详细步骤

第一步&#xff1a;上传nginx压缩包到指定目录。 第二步&#xff1a;解压nginx压缩包。 第三步&#xff1a;配置编译nginx 配置编译方法&#xff1a; ./configure 配置编译后结果信息&#xff1a; 第四步&#xff1a;编译nginx 在nginx源文件目录中直接运行make命令 第五步&…

C++初阶—string类

第一章&#xff1a;为什么要学习string类 1.1 C语言中的字符串 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&…

基于Django的豆瓣影视剧推荐系统的设计与实现

【Django】基于Django的豆瓣影视剧推荐系统的设计与实现&#xff08;完整系统源码开发笔记详细部署教程&#xff09;✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统采用了Python作为后端开发语言&#xff0c;采用Django作为后端架构&#xff0c;结…

【miniconda】:langraph的windows构建

langraph需要python3.11 langraph强烈建议使用py3.11 默认是3.12 官方 下载仓库 下载老版本的python (后续发现新版miniconda也能安装老版本的python) 在这里

使用Python和Qt6创建GUI应用程序--关于Qt的一点介绍

关于Qt的一点介绍 Qt是一个免费的开源部件工具包&#xff0c;用于创建跨平台GUI应用程序&#xff0c;允许应用程序从Windows瞄准多个平台&#xff0c;macOS&#xff0c; Linux和Android的单一代码库。但是Qt不仅仅是一个Widget工具箱和功能内置支持多媒体&#xff0c;数据库&am…

Web3.0时代的挑战与机遇:以开源2+1链动模式AI智能名片S2B2C商城小程序为例的深度探讨

摘要&#xff1a;Web3.0作为互联网的下一代形态&#xff0c;承载着去中心化、开放性和安全性的重要愿景。然而&#xff0c;其高门槛、用户体验差等问题阻碍了Web3.0的主流化进程。本文旨在深入探讨Web3.0面临的挑战&#xff0c;并提出利用开源21链动模式、AI智能名片及S2B2C商城…

NoteGen:记录、写作与AI融合的跨端笔记应用

在信息爆炸的时代,如何高效地捕捉灵感、整理知识并进行创作成为了许多人关注的问题。为此,我们开发了 NoteGen,一款专注于记录和写作的跨端 AI 笔记应用。它基于 Tauri 开发,利用其强大的跨平台能力支持 Mac、Windows 和 Linux 系统,并计划未来扩展到 iOS 和 Android 平台…

八股——Java基础(四)

目录 一、泛型 1. Java中的泛型是什么 ? 2. 使用泛型的好处是什么? 3. Java泛型的原理是什么 ? 什么是类型擦除 ? 4.什么是泛型中的限定通配符和非限定通配符 ? 5. List和List 之间有什么区别 ? 6. 可以把List传递给一个接受List参数的方法吗&#xff1f; 7. Arra…

字节iOS面试经验分享:HTTP与网络编程

字节iOS面试经验分享&#xff1a;HTTP与网络编程 &#x1f31f; 嗨&#xff0c;我是LucianaiB&#xff01; &#x1f30d; 总有人间一两风&#xff0c;填我十万八千梦。 &#x1f680; 路漫漫其修远兮&#xff0c;吾将上下而求索。 目录 字节iOS面试经验分享&#xff1a;HTT…

Jenkins上生成的allure report打不开怎么处理

目录 问题背景&#xff1a; 原因&#xff1a; 解决方案&#xff1a; Jenkins上修改配置 通过Groovy脚本在Script Console中设置和修改系统属性 步骤 验证是否清空成功 进一步的定制 也可以使用Nginx去解决 使用逆向代理服务器Nginx&#xff1a; 通过合理调整CSP配置&a…

【16届蓝桥杯寒假刷题营】第2期DAY5

2.最大公因数 - 蓝桥云课 问题描述 给你2个正整数N&#xff0c;M。 你需要构造一个有N个数的正整数序列a&#xff0c;满足以下条件&#xff1a; ∑i1N​ai​M。 求gcd(a)&#xff0c;可能的最大值。 输入描述 输入一行两个正整数N&#xff0c;M&#xff0c;表示数组的长…

【Linux系统】计算机世界的基石:冯诺依曼架构与操作系统设计

文章目录 一.冯诺依曼体系结构1.1 为什么体系结构中要存在内存&#xff1f;1.2 冯诺依曼瓶颈 二.操作系统2.1 设计目的2.2 系统调用与库函数 一.冯诺依曼体系结构 冯诺依曼体系结构&#xff08;Von Neumann Architecture&#xff09;是计算机的基本设计理念之一&#xff0c;由…

顶刊JFR|ROLO-SLAM:首个针对不平坦路面的车载Lidar SLAM系统

摘要 基于激光雷达&#xff08;LiDAR&#xff09;的同步定位与地图构建&#xff08;SLAM&#xff09;被认为是在恶劣环境中提供定位指导的一种有效方法。然而&#xff0c;现成的基于激光雷达的SLAM方法在经过不平坦地形时&#xff0c;尤其是在垂直方向相关的部分&#xff0c;会…

深度学习探索:ChatGPT数据分析精髓 梯度下降优化方法深度剖析

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…