C++刷LeetCode（1024. 视频拼接）【贪心算法】【递归】
题目描述：你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips 都用区间进行表示：开始于 clips 并于 clips 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 可以剪切成 + + 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
示例 1：
输入：clips = [,,,,,], T = 10
输出：3
解释：
我们选中 , , 这三个片段。
然后，按下面的方案重制比赛片段：
将 再剪辑为 + + 。
现在我们手上有 + + ，而这些涵盖了整场比赛 。
示例 2：
输入：clips = [,], T = 5
输出：-1
解释：
我们无法只用 和 覆盖 的整个过程。
示例 3：
输入：clips = [,,,,,,,,,,,,,,,], T = 9
输出：3
解释：
我们选取片段 , 和 。
示例 4：
输入：clips = [,], T = 5
输出：2
解释：
注意，你可能录制超过比赛结束时间的视频。
提示：
1 <= clips.length <= 100
0 <= clips <= clips <= 100
0 <= T <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/video-stitching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
void currsion(int&res, vector<vector<int> >&clips, int end, vector<int>& visit){
if(end == 0)return;
int temp = -1;
int interval = INT_MIN;
for(int i = 0; i < clips.size(); i++){
if(visit == 0){
if(clips <= end && clips >= end){
if(end - clips > interval){
interval = end - clips;
temp = i;
}
}
}
}
if(temp != -1){
visit = 1;
res++;
currsion(res, clips, clips, visit);
}else{
res = -1;
return;
}
}
int videoStitching(vector<vector<int>>& clips, int T) {
if(T == 0)return 0;
int len = clips.size();
bool temp1 = false, temp2 = false;
for(int i = 0; i < len; i++){
if(clips == 0)temp1 = true;
if(clips >= T || clips >= T)temp2 = true;
}
if(temp1 == false || temp2 == false)return -1;
int res = 0;
vector<int>visit(len, 0);
currsion(res, clips, T, visit);
return res;
}
};
页:
[1]