1024. 視頻拼接（Medium）

前面發(fā)過 幾個視頻，也算是對視頻剪輯入了個門。像我這種非專業(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ū)間問題也就都講完了。

思路分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

代碼實現(xiàn)

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

最終代碼實現(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）。因為當i遞增到n時循環(huán)就會結(jié)束，所以這段代碼只會執(zhí)行O（N）次。

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

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

文章出處：【微信公眾號：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq