給定一個區間的集合
intervals，合併所有重疊的區間，回傳不重疊的區間陣列。
Example:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]
Intuition
TIP
按起點排序後，相鄰區間若重疊就合併，不重疊就開始新區間。
- 排序是關鍵的第一步，排序後只需比較相鄰區間
- 重疊判斷：前一個區間的 end >= 下一個區間的 start
- 合併：更新 end 為兩者的 max
Approaches
1. Sort and Compare Adjacent — O(n log n) / O(n)
- Idea: 排序後遍歷，逐一與結果中最後一個區間比較，決定合併或新增
- Time:
O(n log n)— 排序主導 - Space:
O(n)— 輸出空間
class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
intervals.sortBy { it[0] }
val result = mutableListOf<IntArray>()
for (interval in intervals) {
if (result.isEmpty() || result.last()[1] < interval[0]) {
result.add(interval)
} else {
result.last()[1] = maxOf(result.last()[1], interval[1])
}
}
return result.toTypedArray()
}
}⭐ 2. Sort and Merge (Cleaner Variable Tracking) — O(n log n) / O(n)
- Idea: 用變數追蹤當前合併中的區間邊界，邏輯更清晰
- Time:
O(n log n) - Space:
O(n)— 輸出空間
class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
if (intervals.isEmpty()) return emptyArray()
intervals.sortBy { it[0] }
val result = mutableListOf<IntArray>()
var start = intervals[0][0]
var end = intervals[0][1]
for (i in 1 until intervals.size) {
if (intervals[i][0] <= end) {
end = maxOf(end, intervals[i][1])
} else {
result.add(intArrayOf(start, end))
start = intervals[i][0]
end = intervals[i][1]
}
}
result.add(intArrayOf(start, end))
return result.toTypedArray()
}
}🔑 Takeaways
- Pattern: 排序 + 線性掃描 — 區間問題的經典套路
- Key trick: 排序後只需和前一個區間比較；合併操作就是更新 end 為 max