[57] Insert Interval (TBD)

寫的好醜（哭）

但似算惹XD

至少沒有debug 很久XD 已經可以接受 XD

（標準也太低了吧XD）

上一次寫這題是以放棄作結，所以我可以接受目前的醜版本XD

重點是～它蠻快的呢。（撥瀏海）

（然後看了解答之後覺得自己寫的真的太醜XD

原來可以在一個while裡面，用min 去紀錄 start 要取誰，（小的那個)

跟用max 去紀錄end 要取誰(大的大個）是我想的太複雜了凹屋～～～～

#define min(a,b) (a<b)?a:b

#define max(a,b) (a>b)?a:b

/**

* Return an array of arrays of size *returnSize.

* The sizes of the arrays are returned as *returnColumnSizes array.

* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().

*/

int addRet(int count, int start, int end, int **ret)

{

ret[count] = malloc (sizeof (int)*2);

ret[count][0]= start;

ret[count][1]= end;

return (count+1);

}

int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes){

int **ret = malloc (sizeof (int*)*(intervalsSize+2));

*returnColumnSizes = malloc(sizeof(int)*(intervalsSize+2));

int newCount=0;

int flag = 0;

int start,end;

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

{

if (flag)

{

newCount = addRet(newCount,intervals[i][0],intervals[i][1],ret);

continue;

}

if (newInterval[0]<intervals[i][0] && newInterval[1]<intervals[i][0])

{

newCount = addRet(newCount,newInterval[0],newInterval[1],ret);

newCount = addRet(newCount,intervals[i][0],intervals[i][1],ret);

flag = 1;

}

else if (newInterval[0]>=intervals[i][0] && newInterval[0]<=intervals[i][1])

{

int start = intervals[i][0];

int end = newInterval[1];

if (newInterval[1]<=intervals[i][1])

end = intervals[i][1];

else

{

int j=0;

for (j=i+1;j<intervalsSize;j++)

{

if (newInterval[1]>intervals[j][1])

continue;

if (newInterval[1] < intervals[j][0])

{

end = newInterval[1];

j--;

}

else if (newInterval[1] == intervals[j][0])

end = intervals[j][1];

else if (newInterval[1] <= intervals[j][1])

end = intervals[j][1];

break;

}

i = j;

}

newCount = addRet(newCount,start,end,ret);

flag=1;

}

else if (newInterval[0]> intervals[i][1])

{

newCount = addRet(newCount,intervals[i][0],intervals[i][1],ret);

continue;

}

else if (newInterval[0]< intervals[i][0] && newInterval[1]< intervals[i][1])

{

newCount = addRet(newCount,newInterval[0],intervals[i][1],ret);

flag=1;

}

}

if (!flag)

newCount = addRet(newCount,newInterval[0],newInterval[1],ret);

*returnSize= newCount;

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

(*returnColumnSizes)[i]= 2;

return ret;

}

附在最後面吧供參. 總共有三種case，在前面，當重疊時，在後面

此為case2 重疊時！

		//case 2: overlapping case and merging of intervals
        while(i < n && newInterval[1] >= intervals[i][0]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }