YouTube 影片筆記
Leetcode 合併區間從暴力法推到排序解法並示範 C++ 與 Java 程式碼
原片標題:Merge Intervals | Leetcode | Problem-6 | Brute-Optimal | C++/Java
原片說明
Leetcode 第六題合併區間,我原本以為就是排個序掃一遍,結果 Trevor 光是在開頭問「區間有沒有排序」這件事就講了快一分鐘。這支與其說是解題影片,不如說是在教你面試怎麼開口。他從暴力法 O(n²) 一路推到排序後 O(n log n) 的解法,最後還把 C++ 跟 Java 的程式碼各跑一遍。

影片時間軸
- 00:00開場,點出這是 SDE sheet 第六題合併重疊區間
- 00:44用 1,4 和 4,5 合併成 1,5 說明端點相接也算重疊
- 01:28進入暴力法,排序後對每個區間回頭找誰跟它重疊
- 03:36換最佳解,只留一個暫存區間,邊掃邊合併
- 06:32解釋為什麼排序後重疊區間必定相鄰,這是解法成立的關鍵
- 07:36開始逐行講 C++ 程式碼,包含空輸入的邊界處理
- 09:20接著講 Java 版,改用 start 和 end 兩個變數代替 pair
- 10:43收尾,提醒按讚訂閱,預告下一題

先問清楚區間有沒有排序
這點我覺得是整支影片最實用的地方。Trevor 說題目根本沒講區間有排序,但範例輸入偏偏是排好的,所以面試第一句話就該問。他的理由是面試官不只看你會不會解,還看你會不會想到所有情況。這段雖然拖,但對真的要去面試的人來說,比後面任何一行程式碼都值得記。

暴力法為什麼是 n 平方
排序花 n log n,然後對每個區間都要往後掃一遍看誰跟它重疊,所以整體是 n²。Trevor 講這段的時候把 1,3 併 2,6、8,10 併 9,9 一個個唸過去,好處是讓人真的看懂「重疊」的判斷,缺點是同樣的動作重複太多次,我中間有幾度想快轉。

排序是整個解法能成立的原因
這段是我認為整支影片講得最好的一段。他說因為排過序,只要兩個區間會重疊,它們一定相鄰,所以掃過去遇到不重疊的就代表後面也不可能再重疊,可以直接放進答案。前面那些合併步驟其實都是操作,這裡才是觀念。聽懂這句,程式碼大概就寫得出來了。

兩版程式碼的差異
C++ 版用一個大小為 2 的 vector 當暫存,Java 版則拆成 start 和 end 兩個變數,判斷條件都是「當前區間的左端小於等於暫存的右端」。兩版都有處理空輸入,這點有講到算加分。不過他唸程式碼的速度偏快,邊看邊暫停才跟得上,純用聽的大概會漏掉細節。
值得下載嗎:值得,如果你正在準備面試,這題的「先問排序」跟「為什麼排序後一定相鄰」兩段有反覆看的價值;但如果你只是要一份能跑的程式碼,直接看文字題解會比看二十分鐘影片快。