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