📏 Intervals
排序後合併、插入與重疊判斷。
8 題
📖 分類導讀
區間問題通常需要排序後處理重疊、合併或插入。常見技巧包括按起點排序和掃描線演算法。
Notes:
- 大多數區間題的第一步是按起點排序
- 判斷重疊：a.end >= b.start（排序後）
- 合併區間和插入區間是最基本的操作
排序策略與重疊判斷
絕大多數區間題的第一步是按起點排序（O(n log n)，整題的瓶頸通常就在這裡）。排序後相鄰兩區間 a、b，若 a.end >= b.start 即重疊，可合併成 [a.start, max(a.end, b.end)]。
fun merge(intervals: Array<IntArray>): Array<IntArray> {
intervals.sortBy { it[0] } // 以起點排序，必要時起點相同再比終點
val res = ArrayList<IntArray>()
for (cur in intervals) {
val last = res.lastOrNull()
if (last != null && cur[0] <= last[1]) {
last[1] = maxOf(last[1], cur[1]) // 重疊：延展終點
} else {
res.add(cur.clone()) // 不重疊：開新區間
}
}
return res.toTypedArray()
}IMPORTANT
先問清楚區間是閉（[a, b]，端點相觸算重疊）、開還是半開（[a, b)，相觸不算重疊）。它直接決定重疊判斷該用 >= 還是 >，邊界題常因此出錯。
掃描線
當問題是「任一時刻最多同時有幾個區間」（會議室、航班、天際線）時，改用掃描線：把所有起點與終點拆成事件，按時間排序，起點 +1、終點 -1，掃描時維護當前重疊數的最大值。需要同時知道「誰最早結束」時，常再配一個最小堆追蹤進行中區間的終點。