Merge Intervals – 陪你刷題

Merge Interval 技巧可以有效解決 Overlapping intervals 的問題,這類問題可以衍生為找出 overlapping intervals 或是將 overlapping intervals 合併在一起,解決這類問題前,先歸納出區間之間關係,兩個 interval 之間關係脫不了本文圖中的六種狀況

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

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

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

Leetcode #056 Merge Intervals

演算法:

  1. 依照區間 start 大小來排序所有區間。
  2. 如何判斷兩個區間是否該合併? 依照區間 start 排序後,兩個區間的關係只會剩下 3 種可能性,如下圖,第1種狀況不需要合併,後兩種需要合併,後兩種狀況的共通性在於 B 區間的 start 大於 A 區間的 end 。

  1. 合併後區間的 start 跟 end 該如何決定?
    由於按照 start 來排序所有的區間了,所以合併區間的 start 必定是 A 區間的 start ,而合併區間的 end 則由兩區間的 end 的最大值來決定 (對照上圖的後兩種狀況)。
class Solution {
public:
    struct interval_func {
        bool operator () (vector<int>a, vector<int>b)
        {
            return a[0] < b[0];
        }
    } interval_sort;
    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 已經 sorted 過,這是一個很重要的前提,應該充份利用,避免如同方法 1 一樣做多餘的排序。

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

  1. 第一種狀況如同 newInterval 和 1號區間的關係,newInterval 的 start 大於這類區間的 end ,不需要 merge 區間 。
  2. 不屬於第一種狀況,代表接下來的區間的 end 必定大於 newInterval 的 start ,上圖的 2 號跟 3 號區間的 end 均大於 newInterval 的 start ,但前者需要合併,後者卻不用,關鍵差別在於,newInterval 的 end 有大於區間的 start 。
  3. 合併過後的 newInterval 還要持續跟後面區間確認是否需要合併,觀察上圖的 4 號區間,就屬於還需要繼續合併的區間,判斷的標準,同樣是 newInterval 的 end 需要大於區間的 start 。
  4. 接下來的區間的 start 均大於 newInterval 的 end (如同上圖的 3 號區間),不再需要做 merge 動作。

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

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        if (intervals.size () == 0)
        {
            intervals.push_back(newInterval);
            return intervals;
        }
        if (newInterval[0] > intervals.back()[1])
        {
            intervals.push_back(newInterval);
            return intervals;
        }

        vector<vector<int>> result;
        int index = 0;
        /**
         * Add all intervals whose end point are 
         * smaller than the start point of newInerval
         */
        while (index < intervals.size() && 
               intervals[index][1] < newInterval[0])
        {
            result.push_back (intervals[index]);
            index++;
        }

        /**
         * Merge Interval with newInterval if needed
         */
        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);
        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