56. 合并区间

难度：中等

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 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 <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

Reference

题解

首先对区间的起点按照升序排序，之后遍历区间列表，不断检查已合并区间与当前区间是否存在重叠，如果存在重叠，则将两区间合并，否则将已合并区间加入结果集中，当前区间设为已合并区间。

/**
 * 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().
 */
#define MAX(x, y) (x > y ? x : y)
int comp(const void *x, const void *y)
{
    return **(int **)x - **(int **)y;
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    if (intervalsSize == 0)
    {
        *returnSize = 0;
        return NULL;
    }
    qsort(intervals, intervalsSize, sizeof(int *), comp);
    int **ret = (int **)malloc(sizeof(int *) * intervalsSize), i = 0;
    ret[0] = (int *)memcpy(malloc(sizeof(int) * 2), intervals[0], sizeof(int) * 2);
    *returnSize = 0;
    for (i = 1; i < intervalsSize; i++)
    {
        if (ret[*returnSize][1] >= intervals[i][0])
            ret[*returnSize][1] = MAX(intervals[i][1], ret[*returnSize][1]);
        else
            ret[++(*returnSize)] = (int *)memcpy(malloc(sizeof(int) * 2), intervals[i], sizeof(int) * 2);
    }
    (*returnSize)++;
    *returnColumnSizes = (int *)malloc(sizeof(int) * *returnSize);
    for (i = 0; i < *returnSize; i++)
        (*returnColumnSizes)[i] = 2;
    return ret;
}

评论