資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的影片拼接
假設我們有一系列來自持續 T 秒的體育賽事的影片片段。現在這些影片片段可能彼此重疊並且具有不同的長度。這裡每個影片片段 clips[i] 是一個區間 - 它從 clips[i][0] 時間開始，到 clips[i][1] 時間結束。我們可以自由地將這些片段剪輯成片段 - 我們必須找到所需的最小片段數，以便我們可以將片段剪輯成覆蓋整個體育賽事 ([0, T]) 的片段。如果任務不可能，則返回 -1。因此，如果輸入類似於 [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]，並且 T = 10，則輸出將為 3，因為我們可以取片段 [0,2]、[8,10] 和 [1,9]，總共 3 個片段，然後我們可以如下重建體育賽事，我們將 [1,9] 切割成片段 [1,2] + [2,8] + [8,9]。現在我們有片段 [0,2] + [2,8] + [8,10]，它們覆蓋了體育賽事 [0, 10]。
為了解決這個問題，我們將遵循以下步驟 -
建立一個大小為 T + 1 的陣列 v，並將其填充為 – 1
n := clips 的大小
對於 i 從 0 到 n – 1 的範圍
如果 clips[i, 0] > T，則跳到下一個迭代
v[clips[i, 0]] := v[clips[i, 0]] 和 min(clips[i, 1] 和 T) 的最大值
curr := v[0]
如果 v[0] 為 -1，則返回 -1
i := 1，ret := 1 且 next := 0
當 curr < T 且 i <= n 時
當 i <= curr 時
next := next 和 v[i] 的最大值
將 i 增加 1
如果 next = curr 且 next 為 -1，則返回 -1
curr := next
當 curr >= T 時返回 ret，否則返回 – 1
讓我們看看以下實現以獲得更好的理解
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
vector <int> v(T + 1, -1);
int n = clips.size();
for(int i = 0; i < n; i++){
if(clips[i][0] > T)continue;
v[clips[i][0]] = max(v[clips[i][0]], min(clips[i][1],
T));
}
int curr = v[0];
if(v[0] == -1)return -1;
int i = 1;
int ret = 1;
int next = 0;
while(curr < T && i <= n){
while(i <= curr){
next = max(next, v[i]);
i++;
}
if(next == curr || next == -1) return -1;
curr = next;
ret++;
}
return curr >= T? ret : -1;
}
};
main(){
vector<vector<int>> v1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
Solution ob;
cout << (ob.videoStitching(v1, 10));
}輸入
[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]] 10
輸出
3
205 次檢視
