Merge Intervals

LeetCode 56 題意

• 給定一組區間，可能互相重疊，請合併所有重疊區間，並回傳合併後的區間集合。
• Ex.
  Input: [[1,3],[2,6],[8,10],[15,18]]
  Output: [[1,6],[8,10],[15,18]]

解題思路

• 按區間起點排序。
• 依次處理：
  • 如果當前區間與結果最後一個區間重疊，合併。
  • 否則，直接加入結果。
• 時間：O(n log n)（排序主導）
• 空間：O(n)

Kotlin

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    if (intervals.isEmpty()) return arrayOf()
    intervals.sortBy { it[0] }

    val merged = mutableListOf<IntArray>()
    var current = intervals[0]

    for (i in 1 until intervals.size) {
        if (intervals[i][0] <= current[1]) {
            current[1] = maxOf(current[1], intervals[i][1])
        } else {
            merged.add(current)
            current = intervals[i]
        }
    }
    merged.add(current)
    return merged.toTypedArray()
}

Follow-up

• 如何在不排序的情況下處理（例如輸入已經是排序好的）？
• 如果數據量非常大，是否能線上 (streaming) 合併？
• 如何擴展到三維區間 (cube intervals)？