题解 | #合并区间#

/**
 * 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;
}