题解 | #合并区间#
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
/** * struct Interval { * int start; * int end; * }; */ int cmp(const void *a, const void *b) { return (((struct Interval*)a)->start - ((struct Interval*)b)->start); } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param intervals Interval类一维数组 * @param intervalsLen int intervals数组长度 * @return Interval类一维数组 * @return int* returnSize 返回数组行数 */ struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) { //判断合法性 if(intervalsLen == 0) return NULL; if(intervalsLen == 1) { *returnSize = 1; return intervals; } struct Interval* returnintervals = (struct Interval*)malloc(sizeof(struct Interval) * intervalsLen); struct Interval intervalcpy = {0}; int k = 1,i = 0; *returnSize = 0; //排序 qsort(intervals, intervalsLen, sizeof(struct Interval), cmp); //合并 intervalcpy = intervals[0]; while(1) { //若有重叠部分 if(i + k < intervalsLen && intervalcpy.end >= intervals[i + k].start) { if(intervalcpy.end < intervals[i + k].end) intervalcpy.end = intervals[i + k].end; k++; } else //若没有重叠部分 { //将区间存放数组中 returnintervals[(*returnSize)++] = intervalcpy; //判断结束 i + 1 < intervalsLen if(i + k >= intervalsLen) break; intervalcpy = intervals[i + k]; if(i + k == intervalsLen - 1) { returnintervals[(*returnSize)++] = intervalcpy; break; } //判断下一个区间 i = i + k; k = 1; } } return returnintervals; }