題目描述:給定一組區間,合併所有重疊的區間,回傳合併後的結果。
解題思路:先按開始時間排序。然後線性掃描:維護一個「當前合併區間」(初始為第一個區間)。對每個後續區間,若與當前區間重疊(next.start <= curr.end),則擴展 curr.end;否則將 curr 加入結果,開始新的合併區間。
時間複雜度:O(n log n) — 排序主導,合併掃描為 O(n)。
空間複雜度:O(n) — 輸出結果(排序原地進行)。
1. Sort intervals by start time 2. Initialize result with first interval 3. For each subsequent interval: a. If it overlaps with result.back() (start <= back.end): extend back.end b. Else: append interval to result 4. Return result
堆疊方法 O(n log n):排序後遍歷,用堆疊維護不重疊的區間 — 同複雜度但使用額外空間。
貪心無排序:若區間已排序,一次掃描即可 — 但輸入通常未排序。