leetcode.56

C 排序

刷题

发布日期: 2022-03-23

LeetCode 56.合并区间

1 题目描述

题目链接：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 <= start_i <= end_i <= 10^4$

2 思路

套路：直接对某一维进行排序，然后按照某一维的大小关系进行操作即可。

/**
 * 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 cmp(const void *a, const void *b){
    return ((*(int **)a)[0] - (*(int **)b)[0]); //按第一个元素进行排序
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    qsort(intervals, intervalsSize, sizeof(int *), cmp);

    int** ret = (int **)malloc(sizeof(int *) * intervalsSize);
    *returnSize = 0;
    *returnColumnSizes = (int *)malloc(sizeof(int)*intervalsSize);
    int left = intervals[0][0], right = intervals[0][1];
    for(int i = 1; i <= intervalsSize; i++){
        if(i == intervalsSize){                         //说明到了最后一个区间，需要加一个答案
            ret[*returnSize] = (int *)malloc(sizeof(int)*2);
            ret[*returnSize][0] = left;
            ret[*returnSize][1] = right;
            (*returnColumnSizes)[(*returnSize)++] = 2;
        }else if(right >= intervals[i][0]){             //重叠
            right = fmax(right, intervals[i][1]);       //看右端点大小更新right
        }else if(right < intervals[i][0]){
            ret[*returnSize] = (int *)malloc(sizeof(int)*2);
            ret[*returnSize][0] = left;
            ret[*returnSize][1] = right;
            (*returnColumnSizes)[(*returnSize)++] = 2;
            left = intervals[i][0], right = intervals[i][1];
        }
    }
    return ret;
}