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