Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 56. Merge Intervals

---

題目：


解答：

int mysort(const void *pa, const void *pb)
{
    const int** a = (const int**)pa;
    const int** b = (const int**)pb;
 
    if (a[0][0] == b[0][0]) {
        return a[0][1] - b[0][1];
    }
 
    return a[0][0] - b[0][0];
}

int max(int a, int b)
{
    return a > b ? a : b;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes)
{
    int i = 0;
    int p = 0;
    int *cur = NULL;
    int **r = calloc(intervalsSize, sizeof(int *));

    *returnSize = 0;
    *returnColumnSizes = calloc(intervalsSize, sizeof(int));

    qsort(intervals, intervalsSize, sizeof(int *), mysort);
    cur = intervals[0];

    for (i = 1; i < intervalsSize; i++) {
        if (intervals[i][0] <= cur[1]) {
            cur[1] = max(cur[1], intervals[i][1]);
        }
        else {
            p = (*returnSize)++;
            r[p] = calloc(2, sizeof(int));
            memcpy(r[p], cur, sizeof(int) * 2);

            (*returnColumnSizes)[p] = 2;
            cur = intervals[i];
        }
    }

    p = (*returnSize)++;
    r[p] = calloc(2, sizeof(int));
    memcpy(r[p], cur, sizeof(int) * 2);
    (*returnColumnSizes)[p] = 2;
    
    return r;
}