你將會獲得一系列視頻片段，這些片段來自于一項持續時長為 T 秒的體育賽事，這些片段可能有所重疊，也可能長度不一，
視頻片段 clips[i] 都用區間進行表示：開始于 clips[i][0] 并于 clips[i][1] 結束，我們甚至可以對這些片段自由地再剪輯，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分，
我們需要將這些片段進行再剪輯，并將剪輯后的內容拼接成覆寫整個運動程序的片段（[0, T]），回傳所需片段的最小數目，如果無法完成該任務，則回傳 -1 ，
示例 1：
輸入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 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]], T = 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]], T = 9
輸出：3
解釋：
我們選取片段 [0,4], [4,7] 和 [6,9] ，
示例 4：
輸入：clips = [[0,4],[2,8]], T = 5
輸出：2
解釋：
注意，你可能錄制超過比賽結束時間的視頻，
提示：
1 <= clips.length <= 100
0 <= clips[i][0] <= clips[i][1] <= 100
0 <= T <= 100
解題思路：
1024節快樂~
果然今天LeetCode要選擇這道題目，這道題目有兩種方法來解決，第一種是動態規劃的方法，我們令 dp[i]表示將區間 [0,i) 覆寫所需的最少子區間的數量，由于我們希望子區間的數目盡可能少，因此可以將所有 dp[i] 的初始值設為一個大整數，并將 dp[0]（即空區間）的初始值設為 0，我們可以列舉所有的子區間來依次計算出所有的 dp 值，我們首先列舉 i，同時對于任意一個子區間 [aj,bj)，若其滿足 aj < i ≤bj?，那么它就可以覆寫區間 [0,i)的后半部分，而前半部分則可以用 dp[aj]對應的最優方法進行覆寫，因此我們可以用 dp[aj]+1 來更新 dp[i]，這是官方給的解釋，代碼如下：
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
vector<int> dp(T + 1, INT_MAX - 1);
dp[0] = 0;
for (int i = 1; i <= T; i++) {
for (auto& it : clips) {
if (it[0] < i && i <= it[1]) {
dp[i] = min(dp[i], dp[it[0]] + 1);
}
}
}
return dp[T] == INT_MAX - 1 ? -1 : dp[T];
}
};
第二種是基于貪心的演算法，首先找到在左端小于T的情況下，右端能到達的最大值，儲存到容器中，然后遍歷T，如果到達T時右端最大也只能到T，那么說明無法到達終點，回傳-1，用left表示上個子區間的位置，num表示子區間的個數，如果left==i，那么需要一個子區間， num++，代碼如下：
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
// 代表左邊在i的情況下，右邊最遠能滿足的距離
vector<int> right(T);
int left = 0, last = 0, num = 0;
for(vector<int>& it : clips){
// 遍歷查找在左端小于T的情況下，右端能到達的最大值
if(it[0] < T){
right[it[0]] = max(right[it[0]], it[1]);
}
}
// 遍歷一遍T，查找需要切割或者組合的部分
for(int i = 0; i < T; i ++){
last = max(last, right[i]);
if(last == i){
return -1;
}
if(left == i){
num ++;
left = last;
}
}
return num;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/192678.html
標籤：其他
上一篇：信號帶寬與信道帶寬