Interval Scheduling – 陪你刷題

區間調度(Interval Scheduling)是一種在存在大量區間的情況下,有效率地找出一組最大相容子集(Largest Compatible Subset)的演算法。

在進行區間調度演算法之前,我們先定義區間(Interval)和相容(Compatible)的概念。

Interval :包含開始時間和結束時間的區間,且結束時間必定大於開始時間。
Compatible :兩個區間之間沒有重疊。反之,兩個區間為不相容(Incompatible),代表他們之間的時間有重疊。

下圖的 interval 1 和 interval 2 為 incompatible ,而 interval 2 和 interval 3 為 compatible 。

對於這類問題,我們可以將區間想像成資源,我們想做到的是找出能夠最大化使用這些資源的方案。

那該如何有效率地找出一組彼此互不重疊的區間,且這組區間的數量是最多的?
答案是,使用貪婪演算法(Greedy Algorithm)。貪婪演算法的核心思想是,在每次選擇時,都選擇當前最優的方案。

在區間調度問題中,我們可以採用以下貪婪策略:

  • 在所有區間中,選擇結束時間最早的區間。
  • 將與該區間不相容的所有區間剔除。
  • 重複上述步驟,直到所有區間都被處理完畢。

(詳細的證明可以參考 mit 課程 )

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

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

至此,透過應用 interval scheduling 演算法,找出一組最大區間組合包含 4, 5 和 6 號區間,這組區間的大小為 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 scheduling)的貪心算法來解。

區間規劃問題是指從一組區間中選出一個最大的子集,使得子集中的任意兩個區間都不重疊。

在這題中,我們可以將每個氣球視為一個區間。射爆一個氣球就相當於從一個座標射出一支箭,箭可以射爆所有與其重疊的氣球。

因此,我們要找到一個最大的子集,使得子集中的任意兩個氣球都不重疊。這樣,我們就可以用最少的箭數射爆所有氣球。

具體步驟如下:

  1. 將所有氣球按照結束座標排序,從小到大排列。
  2. 選擇第一個氣球作為基準。
  3. 逐個檢查後面的氣球。
    • 如果後面的氣球的開始座標小於基準的結束座標,則表示這兩個氣球重疊。我們可以將後面的氣球捨棄。
    • 否則,則表示這兩個氣球不重疊。我們需要將後面的氣球作為新的基準。
  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

Updated on 2024-03-18 21:58:47 星期一

在〈Interval Scheduling – 陪你刷題〉中有 1 則留言

發佈留言

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