57. Insert Interval

題目 / Problem

中文： 給你一個「互不重疊」的區間陣列 intervals，其中 intervals[i] = [start_i, end_i] 代表第 i 個區間的起點與終點。這個陣列已經依照起點 start_i 由小到大排好序。另外給你一個新的區間 newInterval = [start, end]。

請把 newInterval 插入 intervals，插入後要保證： 1. 陣列仍然依照起點由小到大排序； 2. 陣列仍然沒有任何重疊區間（如果有重疊就要合併起來）。

回傳插入後的陣列。你不需要原地修改，可以新建一個陣列回傳。

English: You are given an array of non-overlapping intervals intervals, where intervals[i] = [start_i, end_i], already sorted in ascending order by start. You are also given a new interval newInterval = [start, end]. Insert it so the array stays sorted by start and still has no overlaps (merge if necessary). Return the resulting array.

約束 / Constraints: - 0 <= intervals.length <= 10^4 - intervals[i].length == 2 - 0 <= start_i <= end_i <= 10^5 - intervals is sorted by start_i ascending. - newInterval.length == 2, 0 <= start <= end <= 10^5

範例 / Example:

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

新區間 [2,5] 與 [1,3] 重疊（因為 2 ≤ 3），合併成 [1,5]；[6,9] 不重疊，原樣保留。

名詞解釋 / Glossary

• 區間 / Interval：一對數字 [start, end]，代表數線上從 start 到 end 的一段範圍。A pair [start, end] describing a segment on the number line.
• 重疊 / Overlap：兩個區間 [a,b] 與 [c,d] 有共同部分。判斷方法：只要 a <= d 且 c <= b 就重疊。Two intervals share points; they overlap iff a <= d && c <= b.
• 合併 / Merge：把多個重疊的區間融合成一個更大的區間，新起點取最小的 start，新終點取最大的 end。Fuse overlapping intervals into one: take the smallest start and largest end.
• 已排序 / Sorted：陣列已經依起點由小到大排好，所以我們只要從左掃到右就能依序處理，不必再自己排序。The input is pre-sorted by start, so a single left-to-right scan suffices.
• 三段式掃描 / Three-phase scan：把處理過程分成「新區間左邊的、與新區間重疊的、新區間右邊的」三段，是本題最直觀的解法。Split the work into intervals strictly before, overlapping with, and strictly after the new interval.
• malloc / 動態配置記憶體（C）：malloc(n) 向系統要一塊 n 位元組的記憶體並回傳指標；用完要用 free 釋放。Requests a block of memory at runtime; pointer returned, freed later.
• 指標 / Pointer（C）：儲存某個位址的變數。int* 指向整數，int** 指向「指向整數的指標」（即二維陣列的每一列）。A variable holding an address; int** is an array of rows.
• vector（C++）：STL 的動態陣列，能自動長大，用 push_back 在尾端加元素。A growable array container with push_back.

思路

最直覺的暴力想法是：把 newInterval 加進原陣列，重新依起點排序，再做一次「合併區間」的標準流程。這當然正確，但排序需要 O(n log n)，而原陣列本來就已經排好序了，等於浪費了這個寶貴的條件。我們可以做到 O(n)。

關鍵觀察是：因為陣列已按起點排序，所有區間從左到右可以自然分成三段。第一段是「完全在新區間左邊」的區間，也就是它的終點比新區間的起點還小（interval.end < newInterval.start），這些完全不重疊，直接照抄到答案。第二段是「與新區間重疊」的區間，只要 interval.start <= newInterval.end（在已通過第一段的前提下），就代表有重疊；對這些區間我們不立刻寫入答案，而是不斷把 newInterval 的起點縮小成兩者較小的 start、終點放大成兩者較大的 end，把它們全部吞進 newInterval 裡。等重疊都吃完了，才把這個膨脹後的 newInterval 寫入答案一次。第三段是「完全在新區間右邊」的區間，把剩下的全部照抄即可。三段各掃一次，總共只走一遍陣列，因此是 O(n)。為什麼這樣安全？因為排序保證一旦某個區間落在新區間右邊，後面的區間起點只會更大、更不可能往回重疊，所以不需要回頭檢查。

The brute-force idea is to append newInterval, re-sort by start, then run the standard "merge intervals" pass — correct, but the sort costs O(n log n) and wastes the fact that the input is already sorted. We can do it in O(n).

The key insight: because the array is sorted by start, the intervals split naturally into three consecutive groups. Group 1 are intervals entirely to the left of the new one (interval.end < newInterval.start); they can't overlap, so copy them straight to the output. Group 2 are intervals that overlap the new one — given we've passed group 1, the test is simply interval.start <= newInterval.end. Instead of writing these out, we absorb each into newInterval by shrinking its start to the smaller start and growing its end to the larger end. Once all overlaps are absorbed, we write the now-expanded newInterval exactly once. Group 3 are the intervals entirely to the right; copy them all. Each group is scanned once, so the whole thing is a single O(n) pass. This is safe because sorting guarantees that once we reach an interval to the right of the new one, every later interval starts even further right and cannot loop back to overlap.

逐步走查 / Walkthrough

以 intervals = [[1,3],[6,9]], newInterval = [2,5] 為例。我們維護一個答案陣列 res、一個索引 i，以及會被不斷更新的 newInterval。

最終答案 res = [[1,5],[6,9]]，與預期相符。注意 [1,3] 雖然起點比新區間小，但因為 3 >= 2 它其實與新區間重疊，所以在第二段被吸收，而不是在第一段被照抄——這正是用 end < start 而非 start < start 當作第一段條件的原因。

Solution — C

/*
 * 演算法 / Algorithm: 三段式線性掃描 / three-phase linear scan.
 * 1) 照抄所有在新區間左邊、不重疊的區間 / copy intervals ending before newInterval.
 * 2) 把所有重疊的區間吸收進 newInterval（取 min start, max end）/ absorb overlaps.
 * 3) 寫入膨脹後的 newInterval，再照抄右邊剩下的 / write merged, then copy the rest.
 */

// 回傳一個 int**（二維陣列），並透過指標回傳列數與每列的欄數
// Returns an int** (2D array); reports row count and per-row sizes via out-pointers.
int** insert(int** intervals, int intervalsSize, int* intervalsColSize,
             int* newInterval, int newIntervalSize,
             int* returnSize, int** returnColumnSizes) {

    // 最壞情況是新區間不與任何區間重疊，結果會有 intervalsSize+1 列
    // Worst case: no overlap, so the answer can have intervalsSize+1 rows.
    int** res = (int**)malloc(sizeof(int*) * (intervalsSize + 1)); // 配置列指標陣列 / allocate row pointers
    *returnColumnSizes = (int*)malloc(sizeof(int) * (intervalsSize + 1)); // 每列欄數都是 2 / each row has 2 cols
    int k = 0; // k 是下一個寫入答案的位置 / k is the next write slot in res
    int i = 0; // i 是掃描原陣列的索引 / i is the scan index into intervals

    // 把 newInterval 複製到區域變數，因為我們會不斷更新它 / copy into locals since we mutate them
    int ns = newInterval[0]; // 新區間起點 / new interval start
    int ne = newInterval[1]; // 新區間終點 / new interval end

    // 第一段：終點比新區間起點還小 → 完全在左邊、不重疊，直接照抄
    // Phase 1: intervals ending before ns are strictly left, copy as-is.
    while (i < intervalsSize && intervals[i][1] < ns) {
        res[k] = (int*)malloc(sizeof(int) * 2);     // 為這一列配置 2 個 int / allocate a 2-int row
        res[k][0] = intervals[i][0];                // 複製起點 / copy start
        res[k][1] = intervals[i][1];                // 複製終點 / copy end
        (*returnColumnSizes)[k] = 2;                // 記錄這列有 2 欄 / record column count
        k++;                                        // 答案位置往後 / advance write slot
        i++;                                        // 掃描位置往後 / advance scan index
    }

    // 第二段：只要起點 <= 新區間終點就重疊，把它吸收進 newInterval
    // Phase 2: while current overlaps, absorb it into [ns, ne].
    while (i < intervalsSize && intervals[i][0] <= ne) {
        if (intervals[i][0] < ns) ns = intervals[i][0]; // 起點取較小者 / keep the smaller start
        if (intervals[i][1] > ne) ne = intervals[i][1]; // 終點取較大者 / keep the larger end
        i++;                                            // 繼續看下一個 / move on
    }

    // 重疊都吃完了，把膨脹後的 newInterval 寫入答案一次
    // Overlaps absorbed; write the merged new interval exactly once.
    res[k] = (int*)malloc(sizeof(int) * 2); // 配置一列 / allocate one row
    res[k][0] = ns;                         // 合併後起點 / merged start
    res[k][1] = ne;                         // 合併後終點 / merged end
    (*returnColumnSizes)[k] = 2;            // 這列也是 2 欄 / 2 columns
    k++;                                    // 往後 / advance

    // 第三段：新區間右邊剩下的全部照抄 / Phase 3: copy everything remaining on the right.
    while (i < intervalsSize) {
        res[k] = (int*)malloc(sizeof(int) * 2); // 配置一列 / allocate a row
        res[k][0] = intervals[i][0];            // 複製起點 / copy start
        res[k][1] = intervals[i][1];            // 複製終點 / copy end
        (*returnColumnSizes)[k] = 2;            // 2 欄 / 2 columns
        k++;
        i++;
    }

    *returnSize = k; // 透過指標回傳實際列數 / report the actual number of rows
    return res;      // 回傳二維答案陣列 / return the 2D answer
}

Solution — C++

/*
 * 演算法 / Algorithm: 三段式線性掃描 / three-phase linear scan.
 * 1) 照抄左邊不重疊的區間 / copy non-overlapping intervals on the left.
 * 2) 把所有重疊的吸收進 newInterval / absorb overlaps via min-start / max-end.
 * 3) 寫入合併結果，再照抄右邊 / push merged interval, then copy the right side.
 */
class Solution {
public:
    // vector<vector<int>> 是「整數向量的向量」，等於可變大小的二維陣列
    // vector<vector<int>> is a vector of int-vectors — a growable 2D array.
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;   // 答案容器，會用 push_back 動態加入 / output, grown via push_back
        int n = intervals.size();  // 區間數量 / number of intervals
        int i = 0;                 // 掃描索引 / scan index

        int ns = newInterval[0];   // 新區間起點（會被更新）/ new start (mutable)
        int ne = newInterval[1];   // 新區間終點（會被更新）/ new end (mutable)

        // 第一段：終點 < 新起點 → 完全在左邊，照抄 / Phase 1: copy intervals strictly left.
        while (i < n && intervals[i][1] < ns) {
            res.push_back(intervals[i]); // 直接把整個區間複製進答案 / push the whole interval
            i++;
        }

        // 第二段：起點 <= 新終點 → 重疊，吸收進 [ns, ne] / Phase 2: absorb overlaps.
        while (i < n && intervals[i][0] <= ne) {
            ns = min(ns, intervals[i][0]); // 起點取較小者 / smaller start wins
            ne = max(ne, intervals[i][1]); // 終點取較大者 / larger end wins
            i++;
        }

        // 寫入合併後的新區間（用 {ns, ne} 直接建構一個 vector<int>）
        // Push the merged interval; {ns, ne} constructs a vector<int> in place.
        res.push_back({ns, ne});

        // 第三段：右邊剩下的全部照抄 / Phase 3: copy the remaining right-side intervals.
        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }

        return res; // 回傳答案 / return the result
    }
};

複雜度 / Complexity

• Time: O(n) — 三個 while 迴圈合起來，每個原區間恰好被處理一次（n 指 intervals 的區間數量），沒有任何巢狀重複掃描，所以線性。The three loops together touch each input interval exactly once (n = number of intervals); no nested rescanning, so it is linear.
• Space: O(n) — 不算回傳值的話只用了幾個變數 O(1)；但答案陣列最多有 n+1 個區間，因此輸出佔 O(n)。Auxiliary work is O(1), but the output holds up to n+1 intervals, so output space is O(n).

Pitfalls & Edge Cases

• 第一段條件用 end < start 而非 start < start / Phase-1 test must compare the current end to the new start. 若誤用起點比較，會把像 [1,3] 這種「起點較小但其實重疊」的區間錯誤照抄，導致漏合併。Comparing starts would wrongly copy an interval like [1,3] that actually overlaps.
• 接觸即重疊（用 <=）/ Touching counts as overlapping (use <=). [1,2] 與 [2,3] 共享端點 2，應合併成 [1,3]；條件若寫成 < 會漏掉這種相鄰情況。If you write < instead of <=, adjacent intervals sharing an endpoint won't merge.
• 空輸入 / Empty input. intervals 可能為空（length 0），此時前兩個迴圈都不執行，直接寫入 newInterval 本身，答案是 [newInterval]，程式自然處理。Loops simply don't run; the merged interval is written, giving [newInterval].
• 新區間在最左或最右 / New interval before all or after all. 若 newInterval 全在左邊，第一段不跑、第二段不跑，立刻寫入後第三段照抄全部；全在右邊則第一段抄完全部後寫入。Both extremes fall out of the same three phases without special-casing.
• C 的記憶體配置 / C allocation sizing. 必須配置 intervalsSize + 1 列（最壞情況不重疊多一列）；少配一格在無重疊時會越界寫入。Allocate n+1 rows or you overflow when nothing merges.
• 務必設定 *returnSize 與 returnColumnSizes / Always set the out-parameters. LeetCode 的 C 介面靠這兩個指標得知答案大小，忘記設定會讀到垃圾值。The harness reads result dimensions from these pointers; forgetting them yields garbage.