Insert Interval

LeetCode 57 題意

• 在一組已排序、不重疊的區間中，插入一個新的區間，並保證最後結果仍然是排序且不重疊的。
• Ex.
  Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
  Output: [[1,5],[6,9]]

thoughts

• 遍歷所有區間，分三類：
  • 完全在 newInterval 左邊 → 直接放入結果。
  • 完全在 newInterval 右邊 → 先把合併好的 newInterval 放入，再放當前區間。
  • 重疊 → 更新 newInterval 的範圍。
• 時間：O(n)
• 空間：O(n)

Kotlin

fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    val result = mutableListOf<IntArray>()
    var interval = newInterval

    for (i in intervals) {
        when {
            i[1] < interval[0] -> result.add(i)  // 在左邊
            i[0] > interval[1] -> {              // 在右邊
                result.add(interval)
                interval = i
            }
            else -> {  // 重疊
                interval[0] = minOf(interval[0], i[0])
                interval[1] = maxOf(interval[1], i[1])
            }
        }
    }
    result.add(interval)
    return result.toTypedArray()
}

Follow-up

• 如果需要頻繁插入，是否該用平衡樹 / Segment Tree 優化？
• 如何處理多維度插入, 例如時間 + 地點？
• 如果輸入規模高達百萬，如何避免 O(n) 的遍歷？