/***************************************************************************************************
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
***************************************************************************************************/
#include<stdio.h>

struct Interval {
    int start;
    int end;
};

/*按区间起点排序*/
int cmp(const void *a , const void *b){
    struct Interval *intval1 = (struct Interval *)a;
    struct Interval *intval2 = (struct Interval *)b;

    return intval1->start - intval2->start;
}

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {
        if(intervalsSize == 0){//数组为0
            *returnSize = 0;
            return NULL;
        }
        if(intervalsSize == 1){//只有一个区间
            *returnSize = 1;
            struct Interval *retIntv = (struct Interval*)malloc(sizeof(struct Interval));
            retIntv[0].start = intervals[0].start;
            retIntv[0].end = intervals[0].end;
            return retIntv;
        }
        qsort(intervals,intervalsSize,sizeof(struct Interval),cmp);//排序

    int length = 0,end = 0;
    int *starts = (int *)malloc(intervalsSize*sizeof(int));
    int *ends = (int *)malloc(intervalsSize*sizeof(int));
    memset(starts,-1,intervalsSize*sizeof(int));
    memset(ends,-1,intervalsSize*sizeof(int));
    for(int i = 0;i < intervalsSize;i++){
        starts[length] = intervals[i].start;
        ends[length] = intervals[i].end;
        while(i < intervalsSize - 1 && ends[length] >= intervals[i + 1].start){//合并前一个终点大于后一个的起点的区间
            i++;
            ends[length] = ends[length] > intervals[i].end ? ends[length] : intervals[i].end;
        }
        length++;
    }

    struct Interval *retIntv = (struct Interval*)malloc(length*sizeof(struct Interval));
    for(int i = 0;i < length;i++){
        retIntv[i].start = starts[i];
        retIntv[i].end = ends[i];
    }

    free(starts);
    free(ends);
    *returnSize = length;
    return retIntv;
}

void main(){
    //[1,3],[2,6],[8,10],[15,18]
    //[1,6],[2,3],[8,10],[15,18]
    //[1,6],[8,10],[2,3],[15,18]
    struct Interval *intervals = (struct Interval *)malloc(1*sizeof(struct Interval));
    intervals[0].start = 1;
    intervals[0].end = 6;
    //intervals[1].start = 5;
    //intervals[1].end = 10;
    //intervals[2].start = 2;
    //intervals[2].end = 3;
    //intervals[3].start = 15;
    //intervals[3].end = 18;
    int length = 0;
    struct Interval *retIntv = merge(intervals,1,&length);
    for(int i = 0;i < length;i++){
        printf("[%d,%d]\n",retIntv[i].start,retIntv[i].end);
    }
    free(intervals);
    free(retIntv);
}