56. Merge Intervals

三种情况：
1, lastend < new.start
add lastend belonged node into result
2, lastend > new.start and lastend > new.end
nothing to do
3, lastend > new.start and lastend < new.end
update lastend to new.end

• 每次循环保存的node都是前一个的，因此退出循环后不要忘记添加最后一个node

/**
 * 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().
 */
int compar(const void *a, const void *b)  
{  
    return  ((struct Interval *)a)->start- ((struct Interval *)b)->start;  
}  
   
struct Interval*merge(struct Interval* intervals, int intervalsSize,int* returnSize)  
{  
    int i;  
    int laststart, lastend;  
    struct Interval *res = NULL;  
    int reslen = 0;  
   
    if(intervalsSize == 0)  return res;  
    qsort(intervals, intervalsSize,sizeof(struct Interval), compar);  
   
    laststart = intervals[0].start;  
    lastend = intervals[0].end;  
     
    for(i = 1; i <intervalsSize; i++)  
    {  
        if(intervals[i].start<= lastend)  
        {  
            if(lastend < intervals[i].end)  // new.start <=lastend< new.end
            {  
                lastend = intervals[i].end;  
            }  
        }  
        else  
        {  
            reslen++;  
            res = realloc(res,reslen*sizeof(struct Interval));  // lastend > new.start
            res[reslen-1].start= laststart;  
            res[reslen-1].end= lastend;  
   
            laststart = intervals[i].start;  
            lastend = intervals[i].end;  
        }  
    }  
     
    reslen++;  
    res = realloc(res, reslen*sizeof(struct Interval));  
    res[reslen-1].start =laststart;  
    res[reslen-1].end =lastend;  
   
    *returnSize = reslen;  
    return res;  
}