题解 | #合并区间#

比较简洁易懂的写法，没申请新的空间。

int cmp(const void *a, const void *b)
{
    return (((struct Interval*)a)->start - ((struct Interval*)b)->start);
}
 
struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {
    int i, k = 1, returnLen = intervalsLen;
    qsort(intervals, intervalsLen, sizeof(struct Interval), cmp);
     
    for (i = 1; i < intervalsLen; i++) {
        if (intervals[i].end <= intervals[i-k].end) {
            returnLen--;
            k++;
        } else if (intervals[i].start <= intervals[i-k].end) {
            intervals[i-k].end = intervals[i].end;
            returnLen--;
            k++;
        } else {
            intervals[i-k+1].start = intervals[i].start;
            intervals[i-k+1].end = intervals[i].end;
        }
    }
 
    *returnSize = returnLen;
    return intervals;
}