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.

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.

解答

• 方法一

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

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

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

合併完的矩陣為：[[1, 12], [15, 19]]

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

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

合併完的矩陣為：[[1, 7], [8, 12], [15, 19]]

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

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

合併完的矩陣為：[[1, 6], [7, 12], [15, 19]]

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

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

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

=> 原有矩陣不需要處理

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

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

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

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

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

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

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

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)

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

空間複雜度: O(n)

ans 拿來儲存答案

• 方法二

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

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

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

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

合併完的矩陣為：[[1, 6], [7, 12]]

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

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

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

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

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

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

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 矩陣

參考資料

56. Merge Intervals · leetcodeleetcode.wang