# 56. Merge Intervals

### Leetcode

#### <https://leetcode.com/problems/merge-intervals/description/>

### 題目

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

&#x20;

**Example 1:**

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

**Example 2:**

<pre><code><strong>Input: intervals = [[1,4],[4,5]]
</strong><strong>Output: [[1,5]]
</strong><strong>Explanation: Intervals [1,4] and [4,5] are considered overlapping.
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

首先我們先來看一個新的元素，如果要加入到原本的矩陣中，會有幾種情況：

假設原本已有的元素為：**`[[1, 6], [8, 12], [15, 19]]`**

1. **新加入的元素為 `[5, 9]`** - 左端點及右端點分別在不同的節點

合併完的矩陣為：`[[1, 12], [15, 19]]`&#x20;

\=> 這種情況會將原有的 `[1, 6]`, `[8, 12]` 刪除，並加入 `[1, 12]` 到矩陣裡

2. **新加入的元素為 `[5, 7]`** - 左端點有對應節點，右端點沒有

合併完的矩陣為：`[[1, 7], [8, 12], [15, 19]]`&#x20;

\=> 將原有的 `[1, 6]` 刪除，，並加入 `[1, 7]` 到矩陣裡

3. **新加入的元素為 `[7, 9]`**  - 右端點有對應節點，左端點沒有

合併完的矩陣為：`[[1, 6], [7, 12], [15, 19]]`&#x20;

\=> 將原有的 `[8, 12]` 刪除，，並加入 `[7, 12]` 到矩陣裡

4. **新加入的元素為 `[9, 10]`** - 左端點及右端點都在同一個節點

合併完的矩陣為：`[[1, 6], [8, 12], [15, 19]]`&#x20;

\=> 原有矩陣不需要處理

5. **新加入的元素為 `[20, 23]`** - 左端點及右端點都不在原有的節點裡

合併完的矩陣為：`[[1, 6], [8, 12], [15, 19], [20, 23]]`

\=> 將新加入的元素直接加進原有矩陣

6. **新加入的元素為 `[1, 100]`** - 左端點及右端點把原有的節點覆蓋了

合併完的矩陣為：`[[1, 100]]`

\=> 根據新加入元素的左右端點，判斷原有矩陣中哪些被覆蓋的元素需要被刪除

列出這六種可能的情況後接著就可以把這些狀況轉換為程式碼了

```javascript
var merge = function (intervals) {
    const ans = [intervals[0]];

    // 將節點從 ans 中移除
    const remove = (node) => {
        const targetIndex = ans.findIndex(item => {
            return item[0] === node[0] && item[1] === node[1]
        });
        if (targetIndex > -1) {
            ans.splice(targetIndex, 1);
        }
    }

    const isValidNodes = (start, end) => {
        return start && end;
    }

    const isSameNode = (start, end) => {
        if (!start && !end) return true
        if (start && !end) return false
        if (!start && end) return false
        return start[0] === end[0] && start[1] === end[1];
    }

    // 從第二個節點開始遍歷每個節點
    for (let i = 1; i < intervals.length; i++) {
        const value = intervals[i];
        let start = null;
        let end = null;

        for (let j = 0; j < ans.length; j++) {
            // 找到左端點在哪個節點
            if (value[0] >= ans[j][0] && value[0] <= ans[j][1]) {
                start = ans[j]
            } 
            // 找到右端點在哪個節點
            if (value[1] >= ans[j][0] && value[1] <= ans[j][1]) {
                end = ans[j]
            } 
            // 判斷哪些節點被覆蓋了
            if (value[0] < ans[j][0] && value[1] > ans[j][1]) {
                // 情況 6. 左端點及右端點把原有的節點覆蓋了
                // 刪除掉這些被覆蓋的元素
                ans.splice(j, 1);
                j--;
            }
        }

        if (isValidNodes(start, end) && !isSameNode(start, end)) {
            // 情況 1. 左端點及右端點分別在不同的節點
            remove(start);
            remove(end);
            ans.push([start[0], end[1]]);
        } else if (start && !end) {
            // 情況 2. 左端點有對應節點，右端點沒有
            remove(start);
            ans.push([start[0], value[1]]);
        } else if (!start && end) {
            // 情況 3. 右端點有對應節點，左端點沒有
            remove(end);
            ans.push([value[0], end[1]]);
        } else if (isValidNodes(start, end) && isSameNode(start, end)) {
            // 情況 4. 左端點及右端點都在同一個節點
        } else if (!start && !end) {
            // 情況 5. 左端點及右端點都不在原有的節點裡
            // 情況 6. 左端點及右端點把原有的節點覆蓋了
            ans.push(value);
        }
    }

    return ans;
};
```

Runtime: 416 ms Beats 5.01% of users with JavaScript

Memory: 59.19 MB Beats 48.59% of users with JavaScript

時間複雜度: O(n^2)&#x20;

要先遍歷一次 `原有的矩陣 (intervals)`，然後又要遍歷 `merge 過後的矩陣 (ans)`

空間複雜度: O(n)&#x20;

`ans` 拿來儲存答案

* **方法二**

可以看到方法一需要列出所有可能的六種情況，接著判斷新加入的元素與每個原有節點之間的關係，這樣寫出一堆 if else 非常的複雜而且也容易出錯

在方法一的過程中，我們需要判斷新加入的元素其左、右端點分別在哪個既有節點上，所以需要去遍歷 `ans` 矩陣，換個方式想，如果一開始就先將矩陣排序好，當把新加入的元素加進來時，只需要判斷其左、右端點跟原有矩陣的最後一個節點之間的關係就好了，如果是這樣的話總共會有以下三種情況：

假設原本已有的元素為：**`[[1, 6]]`**

1. **新加入的元素為 `[7, 12]`** - 新加入元素的左端點比原有元素的右端點大

合併完的矩陣為：`[[1, 6], [7, 12]]`&#x20;

2. **新加入的元素為 `[6, 12]`** - 新加入元素的左端點跟原有元素的右端點一樣大

合併完的矩陣為：`[[1, 12]]`&#x20;

3. **新加入的元素為 `[3, 7]`** - 新加入元素的右端點比原有元素的右端點大

合併完的矩陣為：`[[1, 7]]`&#x20;

4. **新加入的元素為 `[2, 3]`** - 新加入的元素被囊括在原有的元素裡 (剩下的情況)

合併完的矩陣為：`[[1, 6]]`&#x20;

```javascript
var merge = function (intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    const ans = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const last = ans[ans.length - 1];
        const value = intervals[i];

        if (value[0] > last[1]) {
            // 情況 1. 新加入元素的左端點比原有元素的右端點大
            ans.push(value);
        } else if (value[0] === last[1]) {
            // 情況 2. 新加入元素的左端點跟原有元素的右端點一樣大
            last[1] = value[1];
        } else if (value[1] > last[1]) {
            // 情況 3. 新加入元素的右端點比原有元素的右端點大
            last[1] = value[1];
        }
        // 情況 4. 剩下的狀況 - 不需處理
    }

    return ans;
};
```

Runtime: 99 ms Beats 49.59% of users with JavaScript

Memory: 58.58 MB Beats 63.93% of users with JavaScript

時間複雜度: O(nlog(n))  - 排序算法

空間複雜度: O(n) - 存儲 ans 矩陣

### 參考資料

{% embed url="<https://leetcode.wang/leetCode-56-Merge-Intervals.html>" %}
