Merge Intervals – 陪你刷題

使用 Merge Interval 技巧可以有效解決重疊區間的問題。這類問題可以分為找出重疊的區間或將重疊的區間合併在一起。在解決這類問題之前,首先需要歸納區間之間的關係。在本文的圖表中,兩個區間之間的關係可以歸納為六種情況。

Merge Interval 技巧可以有效解決 Overlapping intervals 的問題,這類問題可以衍生為找出 overlapping intervals 或是將 overlapping intervals 合併在一起,解決這類問題前,先歸納出區間之間關係,共有下圖六種狀況:

圖中的 case 2 ~ 5 符合要做區間合併的條件,由此可以了解,如果 a 和 b 區間要合併必定滿足兩個條件:

  1. b 區間的起點 < a 區間的終點
  2. b 區間的終點 > a 區間的起點

遇到 interval 問題時,兩個 interval 之間關係脫不了上圖中的六種狀況,若你需要合併區間,可以透過畫圖方式確認當前是哪種狀況、需不須要合併以及合併後區間的起點跟終點大小該怎麼定。

Leetcode #056 Merge Intervals

演算法:

  1. 依照區間起點大小來排序所有區間。
  2. 如何判斷兩個區間是否該合併? 依照區間起點排序後,兩個區間的關係只剩下如下圖中 3 種可能性,僅後 2 種 case 需要合併,均符合前面所述區間合併的 2 個條件。

  1. 合併後區間的起點跟 end 該如何決定?
    由於按照起點來排序所有的區間了,所以合併區間的起點必定是 A 區間的起點 ,而合併區間的終點則由兩區間的終點的最大值來決定 (對照上圖的後兩種狀況)。
class Solution {
public:
    static bool interval_sort () (vector<int>a, vector<int>b) {
         return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        std::sort (intervals.begin (), intervals.end(), interval_sort);

        vector<vector<int>> result;
        for (int i=0; i<intervals.size(); i++)
        {
            if (result.size() == 0 ||
               result.back()[1] < intervals[i][0])
            {
                result.push_back (intervals[i]);
            }
            else
            {
                result.back()[1] =
                    std::max (result.back()[1], intervals[i][1]);
            }
        }
        return result;
    }
};

時間複雜度

O (n log n)

空間複雜度

O (n)

延伸練習

Leetcode #616, #763

Leetcode #057 Insert Interval

暴力法

直接將 newInterval 加入區間組,再對區間組排序,就等同 Leetcode #56 ,時間複雜度為 O(n log n)

方法 2

原始 intervals 已經排序過,這是一個很重要的前提,應該充分利用,避免像方法 1 一樣做多餘的排序。

遇到 merge interval 類型問題,最煩人的就是要處理各種不同狀況,千萬不要在腦海中自己思考,直接畫圖會是最好的方式,根據下圖,區間與 newInterval 存在 4 種狀況,依序處理這 4 種狀況即可:

  1. 第一種狀況如同 newInterval 和 1 號區間的關係,newInterval 的起點大於 1 號區間的終點 ,不需要 merge 。
  2. 不屬於第一種狀況,代表 newInterval 的起點小於接下來的區間的終點 ,上圖的 2 號, 3 號 跟 4 號區間均符合條件。但僅有 2 跟 4 號需要合併,關鍵條件在於,newInterval 的終點有大於區間的起點 ,就需要做 merge 。
  3. 接下來的區間的起點均大於 newInterval 的終點 (如同上圖的 3 號區間),不需要做 merge 。

將以上四個不同狀況翻譯為程式碼,即可順利解決這類問題。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int index = 0;

        if (intervals.size () == 0)
        {
            intervals.push_back(newInterval);
            return intervals;
        }
        if (newInterval[0] > intervals.back()[1])
        {
            intervals.push_back(newInterval);
            return intervals;
        }

        // Step 1
        while (index < intervals.size() && 
               intervals[index][1] < newInterval[0])
        {
            result.push_back (intervals[index]);
            index++;
        }
        // Step 2
        while (index < intervals.size() &&
               intervals[index][0] <= newInterval[1])
        {
            newInterval[0] =
                std::min (newInterval[0], intervals[index][0]);
            newInterval[1] =
                std::max (newInterval[1], intervals[index][1]);
            index++;
        }
        result.push_back (newInterval);
        // Step 3
        while (index < intervals.size())
        {
            result.push_back (intervals[index]);
            index++;
        }
        return result;
    }
};

時間 & 空間複雜度

均為 O (n) 。

延伸練習

Leetcode #253

結論

碰到這類問題,不需要在腦海中想出所有排列可能性,所有情況都不出第一張圖的六種,冷靜的分析搭配畫圖,就能輕鬆解決這類型題目。
有一點我想要特別分享,我在前篇寫了 Interval Scheduling – 陪你刷題 ,接著馬上寫下本篇介紹 merge intervals ,原因是我在一開始接觸這兩類型題目時,常常搞混他們,甚至覺得這兩種類型題目都屬於同一種,但寫下這兩篇後,我有一個深刻的認知來分辨這兩種類型,Interval scheduling 背後的中心思想是 greedy algorithm ,而 Merge Intervals 背後的中心思想,則是排序陣列並依照區間之間的關係做處理,兩者使用的是截然不同的技巧。

Reference

  1. 14 Patterns to Ace Any Coding Interview Question

Updated on 2024-03-17 19:52:45 星期日

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *