57. Insert Interval

Medium

Description

給定一個已按起點排序且不重疊的區間列表 intervals，以及一個新區間 newInterval。將新區間插入列表中，合併所有重疊的區間，回傳結果列表（仍然按起點排序且不重疊）。

Example:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Intuition#

將區間分成三部分：在新區間之前的、與新區間重疊的（合併）、在新區間之後的。

已排序，所以可以線性掃描
不重疊的直接加入結果
重疊的要合併：取 min(start) 和 max(end)

Approaches#

1: Three-Phase Linear Scan (Straightforward)#

概念: 分三階段處理：加入左邊不重疊的、合併重疊的、加入右邊不重疊的
時間複雜度: O(n)
空間複雜度: O(n) — 輸出空間

class Solution {
    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        val result = mutableListOf<IntArray>()
        var i = 0
        val n = intervals.size

        // 加入所有在 newInterval 之前的區間
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i])
            i++
        }

        // 合併所有與 newInterval 重疊的區間
        val merged = newInterval.copyOf()
        while (i < n && intervals[i][0] <= newInterval[1]) {
            merged[0] = minOf(merged[0], intervals[i][0])
            merged[1] = maxOf(merged[1], intervals[i][1])
            i++
        }
        result.add(merged)

        // 加入所有在 newInterval 之後的區間
        while (i < n) {
            result.add(intervals[i])
            i++
        }

        return result.toTypedArray()
    }
}

⭐2: Single-Pass with Merge Logic#

概念: 一次遍歷，根據當前區間與新區間的關係決定操作，邏輯更緊湊
時間複雜度: O(n)
空間複雜度: O(n) — 輸出空間

class Solution {
    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        val result = mutableListOf<IntArray>()
        var newStart = newInterval[0]
        var newEnd = newInterval[1]
        var inserted = false

        for (interval in intervals) {
            if (interval[1] < newStart) {
                // 當前區間完全在新區間左邊
                result.add(interval)
            } else if (interval[0] > newEnd) {
                // 當前區間完全在新區間右邊
                if (!inserted) {
                    result.add(intArrayOf(newStart, newEnd))
                    inserted = true
                }
                result.add(interval)
            } else {
                // 重疊，擴展合併範圍
                newStart = minOf(newStart, interval[0])
                newEnd = maxOf(newEnd, interval[1])
            }
        }

        if (!inserted) result.add(intArrayOf(newStart, newEnd))
        return result.toTypedArray()
    }
}

🔑 Takeaways#

Pattern: 區間合併 — 判斷兩個區間是否重疊的核心條件：a.start <= b.end && b.start <= a.end
關鍵技巧: 利用輸入已排序的特性，只需線性掃描一次；合併時取起點的 min 和終點的 max