Leetcode 刷題 pattern - Merge Intervals

前言

身在大 CS 時代，有越來越多人投入刷題的行列，在眼花撩亂的題海中，要想有效率地刷題，就需要掌握題目解法中，可以在許多地方應用的觀念，才能以簡禦繁。 Huli 寫的 程式解題新手入門注意事項 和 當我們在學程式時，要學的到底是什麼？ 講得很好，寫題目是為了學會解題的思考法，確保自己掌握重要的資料結構跟演算法。這也是我寫這系列文章的原因，我想把多個散落在各處的題目銜接起來，以後看到相似的問題就可以舉一反三，而不是去背各題目的解法。

舉例來說，之前遇過一題電話面試，問到的題目是：

Input: vector<bool> holidays, int pto
holidays 表示平日或假日，例如 0000011 表示前面 5 天是平日，後面 2 天是假日。
pto 表示最多可以放幾天假。
Output: 計算在可以用完 pto 的情況下，最久可以放多長的假。

範例：holidays = {0,0,0,0,0,1,1}, pto = 2, output = 4 
     因為可以放 {0,0,0,1,1,1,1}

因為學過 Sliding Window 的 pattern，所以這題很快就寫出來了，也順利進到下一關。這個例子明確地讓我知道，我不需要把題目都刷完，而是要掌握解題的思維，接下來應用這些思維就可以解很多變化題。

放上 C++ 程式碼給大家參考：

#include <iostream>
#include <vector>

using namespace std;

int longest_holidays(const vector<bool>& holidays, int pto) {
    int longestHoliday = -1, windowStart = 0;

    for(int windowEnd = 0; windowEnd < holidays.size(); ++windowEnd) {
        if(holidays[windowEnd] == 0) {
            -- pto;   
        }

        // Shrink window size
        while(pto < 0) {
            if(holidays[windowStart++] == 0) {
                ++ pto;
            } 
        }

        // Compare valid window size and longestHoliday
        longestHoliday = max(longestHoliday, windowEnd - windowStart + 1);
    }

    return longestHoliday;
}

int main(){
    // 000001100000110000111
    vector<bool> holidays = {0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1};
    int longest_holiday = longest_holidays(holidays, 9);

    cout << "My longest holiday: " << longest_holiday << ", hooray!\n";

    return 0;
}

上面這題還有一個 follow-up 問題，如果想知道，可以看我的 面經分享。

Merge Intervals 簡介

Merge Interval 的重點就在於，我們需要把所有的 case 都整理出來，然後再思考怎麼寫邏輯，不然就會寫出漏考慮各種 case 的程式。基本上，如果只考慮兩個 interval，就只有下面六種情況：

接下來，我們會討論怎麼應用這些 case。

Merge Intervals 的第一個範例 - Leetcode #252 - Meeting Rooms

題目

Merge Intervals 解法

基本上只要先照開始時間 sort 過，剩下就看看有沒有 overlap 就好，只要 overlap 就 return false。

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        if(intervals.empty()) {
            return true;
        }

        sort(intervals.begin(),intervals.end(),[](vector<int>a, vector<int>b){ 
            return a[0] < b[0];
        });

        for(int i = 0; i < intervals.size() - 1; ++i) {
            if(intervals[i][1] > intervals[i+1][0]) {
                return false;
            }
        }

        return true;
    }
};

這題概念上算是滿簡單的，給大家小試一下身手。

Merge Intervals 的第二個範例 - Leetcode #56 - Merge Intervals

題目

Merge Intervals 解法

首先，我們照上面的方式來分析一下：

會發現，其實如果先 sort 過，我們就只需要考慮三種情況，因為 b 不可能比 a 先開始。然後，如果只需要考慮三種情況，就會發現只有後面兩種需要 merge，而且 merge 完的 interval 的時間必定會是 (a.start, max(a.end, b.end))。

這樣分析完，演算法的邏輯就變得很單純，只要遇到重疊的 intervals，就把兩者 merge 起來；如果沒有重疊，那就把目前的 interval 留在答案中，繼續往下一個 interval 看。參考實作如下：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() < 2) {
            return intervals;
        }

        // Sort the intervals by the start time
        sort(intervals.begin(), intervals.end(), 
             [](const vector<int>& i1, const vector<int>& i2) {
                return i1[0] < i2[0];
        });

        // Keep merging them
        vector<vector<int>> mergedIntervals;
        mergedIntervals.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); ++i) {
            if( mergedIntervals.back()[1] < intervals[i][0] ) {
                mergedIntervals.push_back(intervals[i]);
            }
            else {
                mergedIntervals.back()[1] = max(mergedIntervals.back()[1], intervals[i][1]);
            }
        }

        return mergedIntervals;
    }
};

Merge Intervals 的第三個範例 - Leetcode #57 - Insert Interval

題目

暴力法

我們可以直接把 newInterval append 到 intervals，然後做跟 #56 一樣的事，但是這樣的時間複雜度是 O(NlogN)，浪費了原本 intervals 就是 sorted 的這個性質。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);

        sort(intervals.begin(), intervals.end(), [](const vector<int>& i1, const vector<int>& i2) {
            return i1[0] < i2[0];
        });

        vector<vector<int>> res = {intervals[0]};

        for(int i = 1; i < intervals.size(); ++i) {
            if(res.back()[1] < intervals[i][0]) {
                res.push_back(intervals[i]);
            }    
            else {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
        }

        return res;
    }
};

Merge Intervals 解法

因為 intervals 已經是 sorted，所以我們可以排除掉 end 比 newInterval.start 還要早的所有 interval，然後遇到第一個 end 比 newInterval.start 早的 interval，我們就可以開始 merge。

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

        // Skipping all intervals which ends before newInterval starts
        vector<vector<int>> res;
        while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            ++i;
        }

        // Keep merging until intervals[i] starts after newInterval 
        while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            ++i;
        }
        res.push_back(newInterval);

        // Push all left intervals into the result
        while(i < intervals.size()) {
            res.push_back(intervals[i]);
            ++i;
        }

        return res;
    }
};

這個解法的時間複雜度就下降到 O(N) 了。

總結

今天跟大家介紹了一個新的 pattern - Merge Intervals，上面提供的幾題是讓大家體驗一下。Merge Interval 困難的地方就在於很容易漏掉 corner case。刷題不只是為了通過面試，而是加強自己對資結和演算法的洞見和體驗，進而優雅有效率地解決問題，共勉之。

延伸閱讀

1. Leetcode 刷題 pattern - Two Pointer
2. Leetcode 刷題 pattern - Sliding Window
3. Leetcode 刷題 pattern - Next Greater Element
4. Leetcode 刷題 pattern - Fast & Slow Pointer
5. Leetcode 刷題 pattern - Breadth-First Search

關於作者：
@pojenlai 演算法工程師，對機器人、電腦視覺和人工智慧有少許研究，正致力改善 自己的習慣。