leetcode_56_合并区间

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，

并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路 ： 合并区间思路， 主要是处理第一个和 第二列的处理。

#include
int cmp(const void *a, const void *b) {
    int *qa = *(int **)a;
    int *qb = *(int **)b;
    if(qa[0] == qb[0]) {
        return qa[1] - qb[1];
    }else {
        return qa[0] - qb[0];
    }
}


int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes)
{
    
   // *returnSize = 0; 草了， 这句不能放在这里 ，应该放在异常情况后面，    
    if(intervalsSize == 0) {
        return NULL;
    }

    if(intervalsSize == 1) {
        return intervals;
    }

    //初始化 OUT 入参
    *returnSize = 0;

    int **res = (int **)malloc(sizeof(int *) * intervalsSize);
    int t = -1;

    qsort(intervals, intervalsSize, sizeof(intervals[0]), cmp);
    // 区间合并
    for(int i = 0; i < intervalsSize; i++) {
        res[i] = (int *)malloc(sizeof(int) * 2);
        if(t == -1 || intervals[i][0] > res[t][1]) {
            t++;
            res[t] = intervals[i];
        } else {
            res[t][1] = fmax(res[t][1], intervals[i][1]);
        }
    }

    *returnSize = t + 1;
    *returnColumnSizes = intervalsColSize;
    return res;
}