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

网站建设客服工作网站统计平台

网站建设客服工作,网站统计平台,广州短视频运营营销报价,北京建设工程继续教育网站题目链接 Leetcode.1024 视频拼接 Rating : 1746 题目描述 你将会获得一系列视频片段,这些片段来自于一项持续时长为 time秒的体育赛事。这些片段可能有所重叠,也可能长度不一。 使用数组 clips描述所有的视频片段,其中 clips[i…

题目链接

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
http://www.mnyf.cn/news/45560.html

相关文章:

  • 郴州网站优化seo销售
  • 自己做下载类网站企业文化宣传策划方案
  • 企业网站建设比较好百度快照是怎么做上去的
  • 常德网站开发西安网站seo外包
  • 个人做淘宝客网站要备案搜索引擎优化的主题
  • wordpress 站内通知软文推广公司
  • 做网站需要懂那些软件深圳seo优化排名优化
  • 软件开发流程详细解读温州seo团队
  • 服务器托管专线单页网站怎么优化
  • 织梦网站地图模版百度网盘网页版官网
  • 免费行情软件网站下载无病毒百度推广多少钱一个月
  • 学校网站资源库建设和资源上传互联网营销顾问是做什么的
  • 农业电商网站建设ppt怎么制作自己公司网站
  • wordpress做的著名网站重庆森林粤语
  • 兰州道路建设情况网站专业整站优化
  • 网站开发建设价格附件深圳网络公司推广
  • 网站推广案例app推广全国代理加盟
  • 网站开发者模式怎么打开最全bt搜索引擎
  • 甘肃网站建设方案优化武汉网站开发公司
  • 外贸品牌网站制作2024年小学生简短小新闻
  • 电商网站建设新闻如何做网络推广外包
  • 自动化设计网站建设西安网络推广公司大全
  • 延平网站建设wzjseoseo营销
  • 运城做网站要多少钱百度旗下产品
  • 企业所得税优惠政策最新2023年100万以下辽阳网站seo
  • 怀化找什么人做网站推广渠道平台
  • wordpress 小工具 功能郑州网站优化软件
  • 我想建设一个算命网站自己如何注册网站
  • 网络班级网站建设seo搜索引擎优化题库
  • 北京专业网站设计制作seo学校培训