当前位置:网站首页>LeetCode每日一题(1024. Video Stitching)
LeetCode每日一题(1024. Video Stitching)
2022-07-03 09:01:00 【wangjun861205】
You are given a series of video clips from a sporting event that lasted time seconds. These video clips can be overlapping with each other and have varying lengths.
Each video clip is described by an array clips where clips[i] = [starti, endi] indicates that the ith clip started at starti and ended at endi.
We can cut these clips into segments freely.
For example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event [0, time]. If the task is impossible, return -1.
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
Example 2:
Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We cannot cover [0,5] with only [0,1] and [1,2].
Example 3:
Input: 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
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].
Constraints:
- 1 <= clips.length <= 100
- 0 <= starti <= endi <= 100
- 1 <= time <= 100
先按开始时间对片段进行排序, 如果开始时间相同则按结束时间倒序排序, 然后维护一个栈,保存需要进行拼接的片段, 遍历已排好序的片段, 考虑如下几种情况:
- 当前片段结束时间小于等于栈顶的结束时间, 当前片段不入栈
- 当前片段结束时间大于栈顶的结束时间,开始时间大于栈顶-1 的结束时间, 当前片段正常入栈
- 当前片段结束时间大于栈顶的结束时间,开始时间小于等于栈顶-1 的结束时间, 弹栈, 直到不符合此条件的时候,当前片段入栈
其他细节方面要注意的是片段必须有开始时间为 0 并且有一定时间跨度的片段,否则不可能完成拼接, 遍历过程中, 如果栈顶的结束时间大于等于 time 了那就不需要继续遍历了
impl Solution {
pub fn video_stitching(mut clips: Vec<Vec<i32>>, time: i32) -> i32 {
clips.sort_by(|a, b| {
if a[0] == b[0] {
return b[1].cmp(&a[1]);
}
a[0].cmp(&b[0])
});
if clips.first().unwrap()[0] != 0 {
return -1;
}
let mut stack: Vec<Vec<i32>> = Vec::new();
'outer: for c in clips {
while let Some(last) = stack.pop() {
if last[1] >= time {
stack.push(last);
break 'outer;
}
if c[0] > last[1] || c[1] <= last[1] {
stack.push(last);
continue 'outer;
}
if stack.is_empty() {
stack.push(last);
stack.push(c);
continue 'outer;
}
if stack.last().unwrap()[1] >= c[0] {
continue;
}
stack.push(last);
break;
}
stack.push(c);
continue;
}
if stack.last().unwrap()[1] < time {
return -1;
}
stack.len() as i32
}
}
边栏推荐
- LeetCode 1089. Duplicate zero
- Notes on numerical analysis (II): numerical solution of linear equations
- ERROR: certificate common name “www.mysql.com” doesn’t match requested host name “137.254.60.11”.
- Low code momentum, this information management system development artifact, you deserve it!
- Go language - IO project
- MySQL installation and configuration (command line version)
- [kotlin learning] classes, objects and interfaces - define class inheritance structure
- Beego learning - JWT realizes user login and registration
- The less successful implementation and lessons of RESNET
- Crawler career from scratch (3): crawl the photos of my little sister ③ (the website has been disabled)
猜你喜欢
How to check whether the disk is in guid format (GPT) or MBR format? Judge whether UEFI mode starts or legacy mode starts?
On February 14, 2022, learn the imitation Niuke project - develop the registration function
【点云处理之论文狂读经典版13】—— Adaptive Graph Convolutional Neural Networks
[point cloud processing paper crazy reading frontier version 10] - mvtn: multi view transformation network for 3D shape recognition
2022-1-6 Niuke net brush sword finger offer
Vscode编辑器右键没有Open In Default Browser选项
低代码前景可期,JNPF灵活易用,用智能定义新型办公模式
MySQL installation and configuration (command line version)
[advanced feature learning on point clouds using multi resolution features and learning]
【点云处理之论文狂读经典版14】—— Dynamic Graph CNN for Learning on Point Clouds
随机推荐
[point cloud processing paper crazy reading classic version 7] - dynamic edge conditioned filters in revolutionary neural networks on Graphs
[graduation season | advanced technology Er] another graduation season, I change my career as soon as I graduate, from animal science to programmer. Programmers have something to say in 10 years
[set theory] order relation (chain | anti chain | chain and anti chain example | chain and anti chain theorem | chain and anti chain inference | good order relation)
2022-2-14 learning xiangniuke project - Session Management
Data mining 2021-4-27 class notes
What are the stages of traditional enterprise digital transformation?
2022-2-14 learning xiangniuke project - generate verification code
Principles of computer composition - cache, connection mapping, learning experience
2022-1-6 Niuke net brush sword finger offer
[point cloud processing paper crazy reading cutting-edge version 12] - adaptive graph revolution for point cloud analysis
Save the drama shortage, programmers' favorite high-score American drama TOP10
[point cloud processing paper crazy reading classic version 8] - o-cnn: octree based revolutionary neural networks for 3D shape analysis
ERROR: certificate common name “www.mysql.com” doesn’t match requested host name “137.254.60.11”.
dried food! What problems will the intelligent management of retail industry encounter? It is enough to understand this article
【Kotlin学习】类、对象和接口——带非默认构造方法或属性的类、数据类和类委托、object关键字
【点云处理之论文狂读经典版9】—— Pointwise Convolutional Neural Networks
【点云处理之论文狂读经典版13】—— Adaptive Graph Convolutional Neural Networks
Solve POM in idea Comment top line problem in XML file
【点云处理之论文狂读经典版8】—— O-CNN: Octree-based Convolutional Neural Networks for 3D Shape Analysis
CSDN markdown editor help document