題目

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

分析

跟上一道題的思路一樣，直接把需要插入的區(qū)間和之前的區(qū)間進(jìn)行排序恩袱，然后使用上道題的程序跑就可以授艰。不明白這道題為啥標(biāo)的是Hard，而上道題是Medium症歇。

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

    while(i < j)                               /*控制在當(dāng)組內(nèi)尋找一遍*/
    {
        while(i < j && key <= a[j].start)
        /*而尋找結(jié)束的條件就是，1谭梗，找到一個小于或者大于key的數(shù)（大于或小于取決于你想升
        序還是降序）2忘晤，沒有符合條件1的，并且i與j的大小沒有反轉(zhuǎn)*/ 
        {
            j--;/*向前尋找*/
        }

        a[i].start = a[j].start;
        a[i].end=a[j].end;
        /*找到一個這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是
        a[left]激捏，那么就是給key）*/

        while(i < j && key >= a[i].start)
        /*這是i在當(dāng)組內(nèi)向前尋找设塔，同上，不過注意與key的大小關(guān)系停止循環(huán)和上面相反远舅，
        因為排序思想是把數(shù)往兩邊扔闰蛔，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/
        {
            i++;
        }

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

    a[i].start = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/
    a[i].end=temp;
    sort(a, left, i - 1);/*最后用同樣的方式對分出來的左邊的小組進(jìn)行同上的做法*/
    sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進(jìn)行同上的做法*/
                       /*當(dāng)然最后可能會出現(xiàn)很多分左右，直到每一組的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* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
    struct Interval *ans=(struct Interval *)malloc(sizeof(struct Interval)*(intervalsSize+1));
    *returnSize=0;
    struct Interval *temp=(struct Interval *)malloc(sizeof(struct Interval)*(intervalsSize+1));
    for(int i=0;i<intervalsSize;i++)
    {
        temp[i].start=intervals[i].start;
        temp[i].end=intervals[i].end;
    }
    temp[intervalsSize].start=newInterval.start;
    temp[intervalsSize].end=newInterval.end;
    sort(temp,0,intervalsSize);
    int p=temp[0].start,q=temp[0].end;
    for(int i=0;i<=intervalsSize;i++)
    {
        printf("%d %d\n",temp[i].start,temp[i].end);
    }
    for(int i=1;i<=intervalsSize;i++)
    {
        if(q>=temp[i].start)
        {
            if(q<temp[i].end)
                q=temp[i].end;
        }
        else
        {
            ans[*returnSize].start=p;
            ans[*returnSize].end=q;
            *returnSize=*returnSize+1;
            p=temp[i].start;
            q=temp[i].end;
        }
    }
    ans[*returnSize].start=p;
    ans[*returnSize].end=q;
    *returnSize=*returnSize+1;
    return ans;
}