1024. 視頻拼接（Medium）

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

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

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

剪視頻時(shí)，每個(gè)視頻片段都可以抽象成了一個(gè)個(gè)區(qū)間，時(shí)間就是區(qū)間的端點(diǎn)，這些區(qū)間有的相交，有的不相交……

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

這是個(gè)很有意思的區(qū)間算法問(wèn)題，也是力扣第 1024 題「視頻拼接」，題目如下：

函數(shù)簽名如下：

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

記得以前寫過(guò)好幾篇區(qū)間相關(guān)的問(wèn)題：

區(qū)間問(wèn)題合集 寫過(guò)求區(qū)間交集、區(qū)間并集、區(qū)間覆蓋這幾個(gè)問(wèn)題。

貪心算法做時(shí)間管理 寫過(guò)利用貪心算法求不相交的區(qū)間。

算上本文的區(qū)間剪輯問(wèn)題，經(jīng)典的區(qū)間問(wèn)題也就都講完了。

思路分析

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

前文多次說(shuō)過(guò)，區(qū)間問(wèn)題肯定按照區(qū)間的起點(diǎn)或者終點(diǎn)進(jìn)行排序。

因?yàn)榕判蛑蟾菀渍业较噜弲^(qū)間之間的聯(lián)系，如果是求最值的問(wèn)題，可以使用貪心算法進(jìn)行求解。

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

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

為什么這樣排序呢，主要考慮到這道題的以下兩個(gè)特點(diǎn)：

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

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

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

這一條就是貪心的策略，因?yàn)轭}目讓我們計(jì)算最少需要的短視頻個(gè)數(shù)，如果起點(diǎn)相同，那肯定是越長(zhǎng)越好，不要白不要，多出來(lái)了大不了剪輯掉嘛。

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

這樣我們就可以確定，如果clips［0］是的起點(diǎn)是 0，那么clips［0］這個(gè)視頻一定會(huì)被選擇。

當(dāng)我們確定clips［0］一定會(huì)被選擇之后，就可以選出第二個(gè)會(huì)被選擇的視頻：

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

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

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

代碼實(shí)現(xiàn)

實(shí)現(xiàn)上述思路需要我們用兩個(gè)變量curEnd和nextEnd來(lái)進(jìn)行：

最終代碼實(shí)現(xiàn)如下：

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

if （T == 0） return 0;

// 按起點(diǎn)升序排列，起點(diǎn)相同的降序排列

Arrays.sort（clips， （a， b） -》 {

if （a［0］ == b［0］） {

return b［1］ - a［1］;

}

return a［0］ - b［0］;

}）;

// 記錄選擇的短視頻個(gè)數(shù)

int res = 0;

int curEnd = 0， nextEnd = 0;

int i = 0， n = clips.length;

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

// 在第 res 個(gè)視頻的區(qū)間內(nèi)貪心選擇下一個(gè)視頻

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

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

i++;

}

// 找到下一個(gè)視頻，更新 curEnd

res++;

curEnd = nextEnd;

if （curEnd 》= T） {

// 已經(jīng)可以拼出區(qū)間 ［0， T］

return res;

}

}

// 無(wú)法連續(xù)拼出區(qū)間 ［0， T］

return -1;

}

這段代碼的時(shí)間復(fù)雜度是多少呢？雖然代碼中有一個(gè)嵌套的 while 循環(huán)，但這個(gè)嵌套 while 循環(huán)的時(shí)間復(fù)雜度是O（N）。因?yàn)楫?dāng)i遞增到n時(shí)循環(huán)就會(huì)結(jié)束，所以這段代碼只會(huì)執(zhí)行O（N）次。

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

原文標(biāo)題：剪視頻剪出一個(gè)貪心算法…

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

責(zé)任編輯：haq