56. Merge Intervals

Medium
Description

給定一個區間的集合 intervals，合併所有重疊的區間，回傳不重疊的區間陣列。

Example:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

Intuition#

按起點排序後，相鄰區間若重疊就合併，不重疊就開始新區間。

  • 排序是關鍵的第一步，排序後只需比較相鄰區間
  • 重疊判斷：前一個區間的 end >= 下一個區間的 start
  • 合併：更新 end 為兩者的 max

Approaches#

1: Sort and Compare Adjacent#

  • 概念: 排序後遍歷，逐一與結果中最後一個區間比較，決定合併或新增
  • 時間複雜度: O(n log n) — 排序主導
  • 空間複雜度: 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) — 輸出空間
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: 排序 + 線性掃描 — 區間問題的經典套路
  • 關鍵技巧: 排序後只需和前一個區間比較；合併操作就是更新 end 為 max
Backward Intervals 57. Insert Interval Forward