yoruru的努力日記

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

SOL：

這一題的解題思路很簡單暴力，排序完輸入的Intervals，接下來兩兩比較Interval：[x1, y1]、[x2, y2]，若 y1>= x2，則代表這兩個區間有重疊(overlap)，那我們就取 max(y1, y2) 做為新y1。

參考影片：

leetcode 中文 | LeetCode 56. Merge Intervals - Python思路總結
↑ 今天比昨天厲害 的思路講解很清楚，但python語法，跟C的寫法差有點多 ><

花花酱 LeetCode 56. Merge Intervals - 刷题找工作 EP85
↑ 花花的C++寫法很簡潔，好看！（說明也很簡潔，但因為太簡潔了，我比較不容易想明白，所以才需要 今天比昨天厲害 的思路講解）

雖然有C++的答案，但跟C語言的寫法還是略有差異，所以我也找了C的解法來交互參考。

A simple C solution[Accepted]

這一題的大難關之一，就是用qsort，否則就要自己寫sort，有點麻煩XD

[101北一資訊集訓] 06_2 qsort()函式

Using qsort() To Sort An Array | C Programming Example

qsort用法--完整版(解释了cmp)【转】

sort後，接下來就是取max，C++可以直接用max函數，C語言則是用fmax。

或者用巨集也可以（不過還是內建的函式庫比較好吧？

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

↑ 函數：取大值 max(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 cmp(const void *p1, const void *p2)
{
    if(((int**)p1)[0][0]==((int**)p2)[0][0])
        return (((int**)p1)[0][1]-((int**)p2)[0][1]);
    return (((int**)p1)[0][0]-((int**)p2)[0][0]);
}
int* addInterval(int a, int b){
    int* I =(int*)malloc(sizeof(int)*2);
    I[0]=a;
    I[1]=b;
    return I;
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){

    if(intervalsSize==0)
        return NULL;
    
    qsort(intervals,intervalsSize,sizeof(intervals[0]),cmp);

    int **result = (int**)malloc(sizeof(int*)*intervalsSize);
    *returnSize = 0;

    result[*returnSize]=addInterval(intervals[0][0],intervals[0][1]);

    for(int i=1; i<intervalsSize; i++){
        if(result[*returnSize][1]>=intervals[i][0])
            result[*returnSize][1] = fmax(result[*returnSize][1],intervals[i][1]);
        else
            result[++(*returnSize)]=addInterval(intervals[i][0],intervals[i][1]);
    }
    (*returnSize)++;
    returnColumnSizes[0]=(int*)malloc((*returnSize)*sizeof(int));
    for(int i=0;i<(*returnSize);i++){
        returnColumnSizes[0][i]=2;
    }
    return result;
}

有點難懂的其實是雙指標，首先舉個例子說明：

int** intervals:[[1,3],[2,6],[8,10],[15,18]]

intervalsSize:4

*intervalsColSize:[2,2,2,2]

intervalsColSize 會是一個指標的原因就是因為它會記錄每區間的大小(共有intervalsSize個)。

這也是為什麼最後returnColumnSizes還要malloc以及給值2。

以 output：[[1,6],[8,10],[15,18]] 來說 returnColumnSizes會長這樣：[[2,2,2]]。