题目

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].

分析

给定一组区间，合并所有重复的区间。然后以左端点排序，依次判断两个区间是否出现重复，合并或者保存即可。

void sort(struct Interval *a, int left, int right)//快速排序
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left].start;
    int temp=a[left].end;

    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j].start)
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }

        a[i].start = a[j].start;
        a[i].end=a[j].end;
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/

        while(i < j && key >= a[i].start)
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }

        a[j].start = a[i].start;
        a[j].end=a[i].end;
    }

    a[i].start = key;/*当在当组内找完一遍以后就把中间数key回归*/
    a[i].end=temp;
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

/**
 * 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) {
    struct Interval *ans=(struct Interval *)malloc(sizeof(struct Interval)*intervalsSize);
    if(intervalsSize==0)
        return ans;
    *returnSize=0;
    sort(intervals,0,intervalsSize-1);
    int p=intervals[0].start,q=intervals[0].end;
    //for(int i=0;i<intervalsSize;i++)
    //{
    //    printf("%d %d\n",intervals[i].start,intervals[i].end);
    //}
    for(int i=1;i<intervalsSize;i++)
    {
        if(q>=intervals[i].start)
        {
            if(q<intervals[i].end)
                q=intervals[i].end;
        }
        else
        {
            ans[*returnSize].start=p;
            ans[*returnSize].end=q;
            *returnSize=*returnSize+1;
            p=intervals[i].start;
            q=intervals[i].end;
        }
    }
    ans[*returnSize].start=p;
    ans[*returnSize].end=q;
    *returnSize=*returnSize+1;
    return ans;
}