題目描述:給定按開始時間排序的非重疊區間列表和一個新區間,插入並合併重疊區間。
解題思路:線性掃描分三個階段:(1)加入所有在新區間左側的(end < newStart);(2)合併所有與新區間重疊的(start <= newEnd);(3)加入剩餘的。合併時不斷擴展新區間的 start 和 end。無需排序,直接線性 O(n)。
時間複雜度:O(n) — 單次線性掃描。
空間複雜度:O(n) — 輸出結果陣列(不計輸出的話為 O(1))。
1. Add all intervals ending before newInterval starts 2. Merge all overlapping intervals with newInterval (extend boundaries) 3. Add merged newInterval 4. Add all remaining intervals 5. Return result
使用 merge intervals:將新區間加入,再調用 merge — 簡單但 O(n log n)。
一次掃描 O(n):不排序,直接遍歷並跟蹤狀態(插入前、重疊、插入後)— 最優但邏輯複雜。