1024. 視頻拼接（Medium）

前面發過 幾個視頻，也算是對視頻剪輯入了個門。像我這種非專業剪輯玩家，不做什么宏大特效電影鏡頭，只是做個視頻教程，其實也沒啥難度，只需要把視頻剪流暢，所以用到最多的功能就是切割功能，然后刪除和拼接視頻片接。

沒有剪過視頻的讀者可能不知道，在常用的剪輯軟件中視頻被切割成若干片段之后，每個片段都可以還原成原始視頻。

就比如一個 10 秒的視頻，在中間切一刀剪成兩個 5 秒的視頻，這兩個五秒的視頻各自都可以還原成 10 秒的原視頻。就好像蚯蚓，把自己切成 4 段就能搓麻，把自己切成 11 段就可以湊一個足球隊。

剪視頻時，每個視頻片段都可以抽象成了一個個區間，時間就是區間的端點，這些區間有的相交，有的不相交……

假設剪輯軟件不支持將視頻片段還原成原視頻，那么如果給我若干視頻片段，我怎么將它們還原成原視頻呢？

這是個很有意思的區間算法問題，也是力扣第 1024 題「視頻拼接」，題目如下：

函數簽名如下：

int videoStitching（int［］［］ clips， int T）;

記得以前寫過好幾篇區間相關的問題：

區間問題合集 寫過求區間交集、區間并集、區間覆蓋這幾個問題。

貪心算法做時間管理 寫過利用貪心算法求不相交的區間。

算上本文的區間剪輯問題，經典的區間問題也就都講完了。

思路分析

題目并不難理解，給定一個目標區間和若干小區間，如何通過裁剪和組合小區間拼湊出目標區間？最少需要幾個小區間？

前文多次說過，區間問題肯定按照區間的起點或者終點進行排序。

因為排序之后更容易找到相鄰區間之間的聯系，如果是求最值的問題，可以使用貪心算法進行求解。

區間問題特別容易用貪心算法，公眾號歷史文章除了 貪心算法之區間調度，還有一篇 貪心算法玩跳躍游戲，其實這個跳躍游戲就相當于一個將起點排序的區間問題，你細品，你細品。

至于到底如何排序，這個就要因題而異了，我做這道題的思路是先按照起點升序排序，如果起點相同的話按照終點降序排序。

為什么這樣排序呢，主要考慮到這道題的以下兩個特點：

1、要用若干短視頻湊出完成視頻［0， T］，至少得有一個短視頻的起點是 0。

這個很好理解，如果沒有一個短視頻是從 0 開始的，那么區間［0， T］肯定是湊不出來的。

2、如果有幾個短視頻的起點都相同，那么一定應該選擇那個最長（終點最大）的視頻。

這一條就是貪心的策略，因為題目讓我們計算最少需要的短視頻個數，如果起點相同，那肯定是越長越好，不要白不要，多出來了大不了剪輯掉嘛。

基于以上兩個特點，將clips按照起點升序排序，起點相同的按照終點降序排序，最后得到的區間順序就像這樣：

這樣我們就可以確定，如果clips［0］是的起點是 0，那么clips［0］這個視頻一定會被選擇。

當我們確定clips［0］一定會被選擇之后，就可以選出第二個會被選擇的視頻：

我們會比較所有起點小于clips［0］［1］的區間，根據貪心策略，它們中終點最大的那個區間就是第二個會被選中的視頻。

然后可以通過第二個視頻區間貪心選擇出第三個視頻，以此類推，直到覆蓋區間［0， T］，或者無法覆蓋返回 -1。

以上就是這道題的解題思路，仔細想想，這題的核心和前文 貪心算法玩跳躍游戲 寫的跳躍游戲是相同的，如果你能看出這兩者的聯系，就可以說理解貪心算法的奧義了。

代碼實現

實現上述思路需要我們用兩個變量curEnd和nextEnd來進行：

最終代碼實現如下：

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］;

}）;

// 記錄選擇的短視頻個數

int res = 0;

int curEnd = 0， nextEnd = 0;

int i = 0， n = clips.length;

while （i 《 n && clips［i］［0］ 《= curEnd） {

// 在第 res 個視頻的區間內貪心選擇下一個視頻

while （i 《 n && clips［i］［0］ 《= curEnd） {

nextEnd = Math.max（nextEnd， clips［i］［1］）;

i++;

}

// 找到下一個視頻，更新 curEnd

res++;

curEnd = nextEnd;

if （curEnd 》= T） {

// 已經可以拼出區間 ［0， T］

return res;

}

}

// 無法連續拼出區間 ［0， T］

return -1;

}

這段代碼的時間復雜度是多少呢？雖然代碼中有一個嵌套的 while 循環，但這個嵌套 while 循環的時間復雜度是O（N）。因為當i遞增到n時循環就會結束，所以這段代碼只會執行O（N）次。

但是別忘了我們對clips數組進行了一次排序，消耗了O（NlogN）的時間，所以本算法的總時間復雜度是O（NlogN）。

原文標題：剪視頻剪出一個貪心算法…

文章出處：【微信公眾號：算法與數據結構】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq