// 演算法：先依 start 排序，再從左到右掃描；若下一段的 start <= 目前段的 end 就合併
// （延伸右端點），否則開一個新段。排序 O(n log n)，掃描 O(n)。
// Algorithm: sort by start, sweep left to right; if the next start <= current end,
// merge by extending the right end, otherwise begin a new segment.

#include <stdlib.h>  // 提供 malloc / free / qsort / Provides malloc, free, qsort

// 比較函式：告訴 qsort 兩個區間如何排序，依 start 由小到大
// Comparator: tells qsort how to order two intervals, ascending by start
static int cmp(const void *a, const void *b) {
    // a、b 實際上是「指向 int* 的指標」，因為每個元素本身是 int*（一個區間）
    // a and b really point to int* elements (each element is an int* = one interval)
    int *ia = *(int **)a;            // 取出第一個區間的指標 / dereference to first interval
    int *ib = *(int **)b;            // 取出第二個區間的指標 / dereference to second interval
    return ia[0] - ib[0];            // 比較起點；負數表示 ia 排前面 / compare starts
}

// LeetCode 簽名：回傳二維陣列；用 returnSize 回傳列數，returnColumnSizes 回傳每列長度
// LeetCode signature: returns a 2-D array; report row count via returnSize,
// per-row lengths via returnColumnSizes.
int** merge(int** intervals, int intervalsSize, int* intervalsColSize,
            int* returnSize, int** returnColumnSizes) {
    // 先把區間依 start 排序，重疊者就會彼此相鄰
    // Sort intervals by start so overlapping ones become adjacent
    qsort(intervals, intervalsSize, sizeof(int *), cmp);

    // 最多就是輸入的列數（完全不重疊時），先配置這麼多空間
    // At most intervalsSize rows (when nothing merges); allocate that many
    int **result = (int **)malloc(sizeof(int *) * intervalsSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * intervalsSize);

    int k = 0;  // k 是結果中目前的列數，也是下一個寫入位置 / count of result rows so far

    for (int i = 0; i < intervalsSize; i++) {
        // 判斷是否要合併：k>0 表示已有段；且新 start <= 目前段的 end 代表重疊
        // Merge if there is a current segment (k>0) and new start <= its end
        if (k > 0 && intervals[i][0] <= result[k - 1][1]) {
            // 重疊：延伸右端點為兩者較大值 / overlap: extend end to the larger one
            if (intervals[i][1] > result[k - 1][1]) {
                result[k - 1][1] = intervals[i][1];
            }
        } else {
            // 不重疊：開新段，配置一個有 2 格的陣列存 [start, end]
            // No overlap: start a new segment; allocate a 2-slot array for [start, end]
            result[k] = (int *)malloc(sizeof(int) * 2);
            result[k][0] = intervals[i][0];   // 複製起點 / copy start
            result[k][1] = intervals[i][1];   // 複製終點 / copy end
            (*returnColumnSizes)[k] = 2;      // 這一列長度固定為 2 / this row has 2 columns
            k++;                              // 前進到下一個寫入位置 / advance write slot
        }
    }

    *returnSize = k;  // 回報實際合併後的列數 / report the real number of merged rows
    return result;
}