在一個區間內有許多 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)