[56] Merge Intervals

雖然完全是一個不能被接受的慢Orz
但畢竟是我寫的啊啊啊就像我的孩子一樣啊啊啊～～～～～
這個題目描述的太簡單了QQ 有很多疑問
不確定輸入的資料究竟會如何
兩兩一組的array, 要把重疊的部分merge起來
最後輸出merge完以後的兩兩一組的array
(有解釋跟沒解釋一樣 XD)
但總而言之
寫到中等難度就要花掉一天,
我怎麼不去賣雞排呢？

Merge Intervals

/**

 * 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().

 */

void mySort(int* array, int size)

{

    int i,tmp;

    for(i=size;i>0;i--)

    {

        if(array[i] < array[i-1])

        {

            tmp = array[i];

            array[i] = array[i-1];

            array[i-1] = tmp;

        }

        else

            break;

    }

}

struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {

    if(intervals == NULL || intervalsSize== 0)

        return;

    struct Interval* ret = malloc(sizeof(struct Interval) * intervalsSize);

    *returnSize = 0;

    int* start = malloc(sizeof(int) * intervalsSize);

    int* end = malloc(sizeof(int) * intervalsSize);

    for(int i=0;i<intervalsSize;i++)

    {

        start[i] = intervals[i].start;

        end[i] = intervals[i].end;

        mySort(start,i);

        mySort(end,i);

    }

    int istart=0;

    int iend=0;

    int flag = 0;

    ret[*returnSize].start = start[istart++];

    while (iend < intervalsSize)

    {

        if (start[istart] <= end[iend])

        {

            istart++;

            iend++;

            continue;

        }

        if (istart==intervalsSize)

            break;

        if (end[iend] <= start[istart])

        {

            ret[*returnSize].end =end[iend++];

            *returnSize=*returnSize +1;            

            ret[*returnSize].start =start[istart++];

        }                    

    }

    ret[*returnSize].end = end[intervalsSize-1];

    *returnSize=*returnSize +1;            

    return ret;

}

結果我只是慢在sorting 嗎QQ

就自以為大致上會從小到大input

所以用insertion sort 很快之類的

蠢 ！！！

把sort改成 qsort就快很多了 QQ

int cmp(const void *a , const void *b)

{

    return *(int *)a - *(int *)b;

}

    qsort(start, intervalsSize, sizeof(int), cmp);

    qsort(end, intervalsSize, sizeof(int), cmp);

原來自己還沒有笨的太誇張QQ

覺得安慰 QQ