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 星期一