YTGET

YouTube · Facebook · X · TikTok · Instagram · Threads

Leetcode 合併區間從暴力法推到排序解法並示範 C++ 與 Java 程式碼

YouTube 影片筆記

Leetcode 合併區間從暴力法推到排序解法並示範 C++ 與 Java 程式碼

原片標題:Merge Intervals | Leetcode | Problem-6 | Brute-Optimal | C++/Java

原片說明
Check out TUF+:https://takeuforward.org/plus?source=youtube Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing. Also our other social’s: https://linktr.ee/takeUforward Check out takeUforward website for the sheet and other free resources: takeuforward.org Join our Discord Channel - https://discord.gg/GgyQAGEdbG

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

先問面試官區間有沒有排序
先問面試官區間有沒有排序00:55

影片時間軸

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

先問清楚區間有沒有排序

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

暴力法對每個區間回頭找重疊
暴力法對每個區間回頭找重疊01:28

暴力法為什麼是 n 平方

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

排序後重疊區間必定相鄰
排序後重疊區間必定相鄰06:32

排序是整個解法能成立的原因

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

C++ 用 vector of vectors 回傳答案
C++ 用 vector of vectors 回傳答案07:36

兩版程式碼的差異

C++ 版用一個大小為 2 的 vector 當暫存,Java 版則拆成 start 和 end 兩個變數,判斷條件都是「當前區間的左端小於等於暫存的右端」。兩版都有處理空輸入,這點有講到算加分。不過他唸程式碼的速度偏快,邊看邊暫停才跟得上,純用聽的大概會漏掉細節。

值得下載嗎:值得,如果你正在準備面試,這題的「先問排序」跟「為什麼排序後一定相鄰」兩段有反覆看的價值;但如果你只是要一份能跑的程式碼,直接看文字題解會比看二十分鐘影片快。

覺得這篇筆記有幫助嗎?
YTGet 編輯室|看完影片整理的筆記,細節以原片為準。

連線中

影片封面

擷取畫面

輸入時間點,例如 3:20、3.20 或 200

影片皆已含音訊。檔案越大準備時間越久,完成前請保持頁面開啟。