/*
 * 演算法 / 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
    }
};