什么是貪心算法呢？貪心算法可以認(rèn)為是動態(tài)規(guī)劃算法的一個特例，相比動態(tài)規(guī)劃，使用貪心算法需要滿足更多的條件（貪心選擇性質(zhì)），但是效率比動態(tài)規(guī)劃要高。
比如說一個算法問題使用暴力解法需要指數(shù)級時間，如果能使用動態(tài)規(guī)劃消除重疊子問題，就可以降到多項式級別的時間，如果滿足貪心選擇性質(zhì)，那么可以進(jìn)一步降低時間復(fù)雜度，達(dá)到線性級別的。
什么是貪心選擇性質(zhì)呢，簡單說就是：每一步都做出一個局部最優(yōu)的選擇，最終的結(jié)果就是全局最優(yōu)。注意哦，這是一種特殊性質(zhì)，其實只有一小部分問題擁有這個性質(zhì)。
比如你面前放著 100 張人民幣，你只能拿十張，怎么才能拿最多的面額？顯然每次選擇剩下鈔票中面值最大的一張，最后你的選擇一定是最優(yōu)的。
然而，大部分問題都明顯不具有貪心選擇性質(zhì)。比如打斗地主，對手出對兒三，按照貪心策略，你應(yīng)該出盡可能小的牌剛好壓制住對方，但現(xiàn)實情況我們甚至可能會出王炸。這種情況就不能用貪心算法，而得使用動態(tài)規(guī)劃解決，參見前文 動態(tài)規(guī)劃解決博弈問題。
言歸正傳，本文解決一個很經(jīng)典的貪心算法問題 Interval Scheduling（區(qū)間調(diào)度問題）。給你很多形如[start,end]的閉區(qū)間，請你設(shè)計一個算法，算出這些區(qū)間中最多有幾個互不相交的區(qū)間。
int intervalScheduling(int[][] ints) {}
舉個例子，intvs=[[1,3],[2,4],[3,6]]，這些區(qū)間最多有兩個區(qū)間互不相交，即[[1,3],[3,6]]，你的算法應(yīng)該返回 2。注意邊界相同并不算相交。
這個問題在生活中的應(yīng)用廣泛，比如你今天有好幾個活動，每個活動都可以用區(qū)間[start,end]表示開始和結(jié)束的時間，請問你今天最多能參加幾個活動呢？
這個問題有許多看起來不錯的解決思路，實際上都不能得到正確答案。比如說：
也許我們可以每次選擇可選區(qū)間中開始最早的那個？但是可能存在某些區(qū)間開始很早，但是很長，使得我們錯誤地錯過了一些短的區(qū)間。
或者我們每次選擇可選區(qū)間中最短的那個？或者選擇出現(xiàn)沖突最少的那個區(qū)間？這些方案都能很容易舉出反例，不是正確的方案。
正確的思路其實很簡單，可以分為以下三步：
從區(qū)間集合 intvs 中選擇一個區(qū)間 x，這個 x 是在當(dāng)前所有區(qū)間中結(jié)束最早的（end 最?。?。
把所有與 x 區(qū)間相交的區(qū)間從區(qū)間集合 intvs 中刪除。
重復(fù)步驟 1 和 2，直到 intvs 為空為止。之前選出的那些 x 就是最大不相交子集。
把這個思路實現(xiàn)成算法的話，可以按每個區(qū)間的end數(shù)值升序排序，因為這樣處理之后實現(xiàn)步驟 1 和步驟 2 都方便很多:
現(xiàn)在來實現(xiàn)算法，對于步驟 1，由于我們預(yù)先按照end排了序，所以選擇 x 是很容易的。關(guān)鍵在于，如何去除與 x 相交的區(qū)間，選擇下一輪循環(huán)的 x 呢？
由于我們事先排了序，不難發(fā)現(xiàn)所有與 x 相交的區(qū)間必然會與 x 的end相交；如果一個區(qū)間不想與 x 的end相交，它的start必須要大于（或等于）x 的end：
下面看下代碼：
下面舉例幾道 LeetCode 題目應(yīng)用一下區(qū)間調(diào)度算法。
第 435 題，無重疊區(qū)間：
我們已經(jīng)會求最多有幾個區(qū)間不會重疊了，那么剩下的不就是至少需要去除的區(qū)間嗎？
int eraseOverlapIntervals(int[][] intervals) {
int n = intervals.length;
return n - intervalSchedule(intervals);
}
第 452 題，用最少的箭頭射爆氣球：
其實稍微思考一下，這個問題和區(qū)間調(diào)度算法一模一樣！如果最多有n個不重疊的區(qū)間，那么就至少需要n個箭頭穿透所有區(qū)間：
只是有一點不一樣，在intervalSchedule算法中，如果兩個區(qū)間的邊界觸碰，不算重疊；而按照這道題目的描述，箭頭如果碰到氣球的邊界氣球也會爆炸，所以說相當(dāng)于區(qū)間的邊界觸碰也算重疊：
所以只要將之前的算法稍作修改，就是這道題目的答案：
int findMinArrowShots(int[][] intvs) {
// ...
for (int[] interval : intvs) {
int start = interval[0];
// 把 >= 改成 > 就行了
if (start > x_end) {
count++;
x_end = interval[1];
}
}
return count;
}
這么做的原因也不難理解，因為現(xiàn)在邊界接觸也算重疊，所以start == x_end時不能更新區(qū)間 x。
本文終。對于區(qū)間問題的處理，一般來說第一步都是排序，相當(dāng)于預(yù)處理降低后續(xù)操作難度。但是對于不同的問題，排序的方式可能不同，這個需要歸納總結(jié)，以后再寫寫這方面的文章。
聯(lián)系客服
