Interval Scheduling – 陪你刷題

在一個區間內有許多 interval ,透過 interval scheduling 可以有效率地找出一組 the largest compatiable subset of interval (也可以將 interval 想成 resource)。

先定義 interval 和 compatiable,所謂的 interval 包含開始時間和結束時間 ,且結束時間必定大於開始時間, 而 compatiable 代表兩個 interval 之間沒有重疊,反之,兩個 interval 為 incompatible 代表他們之間的時間有重疊。下圖的 interval 1 和 interval 2 為 incompatible ,而 interval 2 和 interval 3 為 compatible 。

回到問題本身,該如何有效率地找出一組彼此互不重疊的 interval ,且這組 interval 包含最多數量的 interval ?

答案是,貪婪地選結束時間最早的 interval ,每選中一個後,剔除與其 incompatible 的所有區間,不斷重複這個過程直到走訪過所有區間 (詳細的證明可以參考 mit 課程 ),貪婪地選擇結束時間最早這個動作,代表 interval scheduling 背後的核心思想是 greedy algorithm 。

以上圖來看,套用 interval scheduling 演算法的步驟如下:

  1. 第一個結束時間最早的 interval 是 4 號區間,與 4 號重疊的都將被剔除,因此 1 跟 2 號都剔除。
  2. 接著最早的為 5 號區間,與 5 號重疊的 3 號區間也將被剔除。
  3. 接著選擇 6 號區間,因為所有區間都走訪過,結束演算法。

至此,透過應用 interval scheduling 演算法,找出一組最大區間組合包含 4, 5 和 6 號區間,這組區間的 size 為 3,你將無法再找到更大的區間組合。

Leetcode #435 Non-overlapping Intervals

典型的 interval scheduling 問題,所有 incompatible 的區間,屬於題目要找的 overlapping interval ,具體演算法如下:

  1. 先將所有區間依照結尾元素大小來排序
  2. 選擇第一個區間的結尾作為 pivot 。
  3. 依序拜訪每個區間,並比較新區間的 起始元素 和 pivot 。
    1. 如果 pivot 大於新曲間的 起始元素 ,代表找到重複區間。
    2. 反之,將新區間的 結尾元素 作為 pivot 。
class Solution {
public:
    static bool interval_sort (vector<int>& a, vector<int>& b)
    {
        if (a[1] < b[1])
            return true;
        else
            return false;
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() < 2)
            return 0;
        std::sort (intervals.begin(), intervals.end(),
                   interval_sort);

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

時間複雜度

O (n log n) 。排序就花費了 O (n log n) 。

空間複雜度

O (1) 。

Leetcode #452 Minimum number of Arrows to Burst Balloons

這題問"最少"需要多少弓箭就可以將所有氣球射穿? 每個氣球的大小橫跨從 start 到 end ,氣球的大小就如何一個 interval ,可以從任意座標上射出弓箭,但題目要 "最少" 弓箭,意味著每隻弓箭要盡可能射到越多的氣球。

其實這是一題典型的 interval scheduling (間格調度問題) 問題,interval scheduling 從所有 interval 中找出一組最大的 subset,最大的組合意味著沒有任何剩下 interval 可以選,所有的 interval 不是屬於組合裡的,就是跟組合內的區間有重疊,透過 scheduling 選出的每一個 interval ,即是弓箭所要瞄準的氣球。

也可以說,對應到前面的 interval scheduing ,選了一個區間,會將所有重疊區間都一併剔除,也就如同射出一支弓箭,盡可能射中越多氣球的情境。但另一個問題是,在 interval scheduling 選的是結束時間最早的 interval,但弓箭射的是一個 x 軸座標,該如何從整個區間選出 x 軸座標位置呢? 你只要畫個圖就可以知道了,從選中的 interval 的結束位置射出弓箭,就能射到所有與其重疊的區間。

將 interval scheduling 應用到此題, 具體步驟如下

  1. 先將所有區間依照 結尾元素 來排序,才能確保每次射擊都盡可能的射穿愈多氣球。

  2. 選擇第一個 結尾元素 最小的區間作為比較基準。

  3. 往後選擇下一個區間 A,並比對區間 A 和比較基準。

    3.1. 如果區間 A 的 開頭元素 小於比較基準的 結尾元素 ,代表區間 A 和比較基準重疊;

    3.2. 反之,區間 A 應該作為新的比較基準,也代表需要多射一隻弓箭。

  4. 不斷執行步驟 3 直到走訪完所有區間。

class Solution {
public:
    static bool interval_sort (vector<int>& a, vector<int>& b)
    {
        if (a[1] < b[1])
            return true;
        else
        {
            return false;
        }
    }
    int findMinArrowShots(vector<vector<int>>& points) {

        if (points.size() == 0)
            return 0;

        std::sort (points.begin(), points.end(), interval_sort);

        int result = 1;
        int pivot = points[0][1];

        for (int i=1; i<points.size(); i++)
        {
            if (points[i][0] > pivot)
            {
                pivot = points[i][1];
                result++;
            }
        }
        return result;
    }
};

時間複雜度

O (n log n)

空間複雜度

O (1)

Reference

  1. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec01.pdf
  2. MIT 6.046J Interval Scheduling