在一個區間內有許多 interval ，透過 interval scheduling 可以有效率地找出一組 compatiable subset of interval of maximum size (也可以將 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 演算法的步驟如下：
- 第一個結束時間最早的 interval 是 4 號區間，與 4 號重疊的都將被剔除，因此 1 跟 2 號都剔除。
- 接著最早的為 5 號區間，與 5 號重疊的 3 號區間也將被剔除。
- 接著選擇 6 號區間，因為所有區間都走訪過，結束演算法。
至此，透過應用 interval scheduling 演算法，找出一組最大區間組合包含 4, 5 和 6 號區間，這組區間的 size 為 3，你將無法再找到更大的區間組合。
Leetcode #435 Non-overlapping Intervals
典型的 interval scheduling 問題，所有 incompatible 的區間，屬於題目要找的 overlapping interval ，具體演算法如下:
- 先將所有區間依照結尾元素大小來排序
- 選擇第一個區間的結尾作為 pivot 。
- 依序拜訪每個區間，並比較新區間的
起始元素和 pivot 。- 如果 pivot 大於新曲間的
起始元素，代表找到重複區間。 - 反之，將新區間的
結尾元素作為 pivot 。
- 如果 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 應用到此題， 具體步驟如下
-
先將所有區間依照
結尾元素來排序，才能確保每次射擊都盡可能的射穿愈多氣球。 -
選擇第一個
結尾元素最小的區間作為比較基準。 -
往後選擇下一個區間 A，並比對區間 A 和比較基準。
3.1. 如果區間 A 的
開頭元素小於比較基準的結尾元素，代表區間 A 和比較基準重疊；3.2. 反之，區間 A 應該作為新的比較基準，也代表需要多射一隻弓箭。
-
不斷執行步驟 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)