C语言力扣刷题12——合并区间[排序]
C语言力扣刷题12——合并区间[排序]
- 一、博客声明
- 二、题目描述
- 三、解题思路
- 1、知识补充
- 使用qsort函数对二维数组进行排序。
- 2、思路说明
- 四、解题代码（附注释）
一、博客声明
找工作逃不过刷题，为了更好的督促自己学习以及理解力扣大佬们的解题思路，开辟这个系列来记录。代码可能不是自己写的，不求方法最好，只求更多地理解大佬们的解题思路。
二、题目描述
以数组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
三、解题思路
1、知识补充
使用qsort函数对二维数组进行排序。
以二维数组的第一个元素为基准，使用qsort库函数对一维数组的排序，可以看之前的一个博客：C语言力扣刷题3——三数之和[快速排序+双指针]
比较函数写法：
int cmpfun(const void* a, const void* b){return (*(int**)a)[0] - (*(int**)b)[0];
}
qsort函数写法：
qsort(intervals, intervalsSize, sizeof(int*), cmpfun);
2、思路说明
先排序，后逐个比较，根据情况构建返回数组。具体看下面的图片，可能会更清楚。
四、解题代码（附注释）
##比较函数
int cmpfun(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*), cmpfun);int** ret = malloc(sizeof(int*) * intervalsSize);int size = 0;ret[size++] = malloc(sizeof(int) * 2);ret[0][0] = intervals[0][0];ret[0][1] = intervals[0][1];for(int i = 1; i < intervalsSize; i++){if(intervals[i][0] <= ret[size - 1][1]){ret[size-1][1] = fmax(ret[size - 1][1], intervals[i][1]);} else {ret[size++] = malloc(sizeof(int) * 2);ret[size - 1][0] = intervals[i][0];ret[size - 1][1] = intervals[i][1];}}*returnSize = size;*returnColumnSizes =malloc(sizeof(int) * size);for(int i = 0; i < size; i++){(*returnColumnSizes)[i] = 2;}return ret;
}