剪視頻剪出一個貪心算法……
對于非專業(yè)剪輯玩家，不做什么宏大特效電影鏡頭，只是做個視頻教程，其實也沒啥難度，只需要把視頻剪流暢，所以用到最多的功能就是切割功能，然后刪除和拼接視頻片接。
沒有剪過視頻的讀者可能不知道，在常用的剪輯軟件中視頻被切割成若干片段之后，每個片段都可以還原成原始視頻。
就比如一個 10 秒的視頻，在中間切一刀剪成兩個 5 秒的視頻，這兩個五秒的視頻各自都可以還原成 10 秒的原視頻。就好像蚯蚓，把自己切成 4 段就能搓麻，把自己切成 11 段就可以湊一個足球隊。
剪視頻時，每個視頻片段都可以抽象成了一個個區(qū)間，時間就是區(qū)間的端點，這些區(qū)間有的相交，有的不相交……
假設(shè)剪輯軟件不支持將視頻片段還原成原視頻，那么如果給我若干視頻片段，我怎么將它們還原成原視頻呢？
這是個很有意思的區(qū)間算法問題，也是力扣第 1024 題「視頻拼接」，題目如下：
函數(shù)簽名如下：
int videoStitching(int[][] clips, int T);
記得以前寫過好幾篇區(qū)間相關(guān)的問題：
區(qū)間問題合集 寫過求區(qū)間交集、區(qū)間并集、區(qū)間覆蓋這幾個問題。
貪心算法做時間管理 寫過利用貪心算法求不相交的區(qū)間。
算上本文的區(qū)間剪輯問題，經(jīng)典的區(qū)間問題也就都講完了。
思路分析
題目并不難理解，給定一個目標(biāo)區(qū)間和若干小區(qū)間，如何通過裁剪和組合小區(qū)間拼湊出目標(biāo)區(qū)間？最少需要幾個小區(qū)間？
前文多次說過，區(qū)間問題肯定按照區(qū)間的起點或者終點進(jìn)行排序。
因為排序之后更容易找到相鄰區(qū)間之間的聯(lián)系，如果是求最值的問題，可以使用貪心算法進(jìn)行求解。
區(qū)間問題特別容易用貪心算法，公眾號歷史文章除了 貪心算法之區(qū)間調(diào)度，還有一篇 貪心算法玩跳躍游戲，其實這個跳躍游戲就相當(dāng)于一個將起點排序的區(qū)間問題，你細(xì)品，你細(xì)品。
至于到底如何排序，這個就要因題而異了，我做這道題的思路是先按照起點升序排序，如果起點相同的話按照終點降序排序。
為什么這樣排序呢，主要考慮到這道題的以下兩個特點：
1、要用若干短視頻湊出完成視頻[0, T]，至少得有一個短視頻的起點是 0。
這個很好理解，如果沒有一個短視頻是從 0 開始的，那么區(qū)間[0, T]肯定是湊不出來的。
2、如果有幾個短視頻的起點都相同，那么一定應(yīng)該選擇那個最長（終點最大）的視頻。
這一條就是貪心的策略，因為題目讓我們計算最少需要的短視頻個數(shù)，如果起點相同，那肯定是越長越好，不要白不要，多出來了大不了剪輯掉嘛。
基于以上兩個特點，將clips按照起點升序排序，起點相同的按照終點降序排序，最后得到的區(qū)間順序就像這樣：
這樣我們就可以確定，如果clips[0]是的起點是 0，那么clips[0]這個視頻一定會被選擇。
當(dāng)我們確定clips[0]一定會被選擇之后，就可以選出第二個會被選擇的視頻：
我們會比較所有起點小于clips[0][1]的區(qū)間，根據(jù)貪心策略，它們中終點最大的那個區(qū)間就是第二個會被選中的視頻。
然后可以通過第二個視頻區(qū)間貪心選擇出第三個視頻，以此類推，直到覆蓋區(qū)間[0, T]，或者無法覆蓋返回 -1。
以上就是這道題的解題思路，仔細(xì)想想，這題的核心和前文 貪心算法玩跳躍游戲 寫的跳躍游戲是相同的，如果你能看出這兩者的聯(lián)系，就可以說理解貪心算法的奧義了。
代碼實現(xiàn)
實現(xiàn)上述思路需要我們用兩個變量curEnd和nextEnd來進(jìn)行：
最終代碼實現(xiàn)如下：
int videoStitching(int[][] clips, int T) {
if (T == 0) return 0;
// 按起點升序排列，起點相同的降序排列
Arrays.sort(clips, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
// 記錄選擇的短視頻個數(shù)
int res = 0;
int curEnd = 0, nextEnd = 0;
int i = 0, n = clips.length;
while (i < n && clips[i][0] <= curEnd) {
// 在第 res 個視頻的區(qū)間內(nèi)貪心選擇下一個視頻
while (i < n && clips[i][0] <= curEnd) {
nextEnd = Math.max(nextEnd, clips[i][1]);
i++;
}
// 找到下一個視頻，更新 curEnd
res++;
curEnd = nextEnd;
if (curEnd >= T) {
// 已經(jīng)可以拼出區(qū)間 [0, T]
return res;
}
}
// 無法連續(xù)拼出區(qū)間 [0, T]
return -1;
}
這段代碼的時間復(fù)雜度是多少呢？雖然代碼中有一個嵌套的 while 循環(huán)，但這個嵌套 while 循環(huán)的時間復(fù)雜度是O(N)。因為當(dāng)i遞增到n時循環(huán)就會結(jié)束，所以這段代碼只會執(zhí)行O(N)次。
但是別忘了我們對clips數(shù)組進(jìn)行了一次排序，消耗了O(NlogN)的時間，所以本算法的總時間復(fù)雜度是O(NlogN)。
▊《labuladong的算法小抄》
付東來（@labuladong） 著
用喜聞樂見的語言講算法
GitHub 68.8K star的硬核算法教程
（京東限時活動，快快掃碼搶購吧！）
如果喜歡本文 歡迎 在看丨留言丨分享至朋友圈 三連 熱文推薦
▼點擊閱讀原文，查看本書詳情~