Leetcode 刷題 pattern - Merge Intervals


Posted by Po-Jen on 2020-01-16


前言

身在大 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,就只有下面六種情況:

img

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

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

題目

img

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

題目

img

Merge Intervals 解法

首先,我們照上面的方式來分析一下:

img

會發現,其實如果先 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

題目

img

暴力法

我們可以直接把 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 演算法工程師,對機器人、電腦視覺和人工智慧有少許研究,正致力改善 自己的習慣


#Leetcode #algorithm #Software Engineer






訂閱電子報




Comment