什么是貪心算法呢卡者？
貪心算法可以認(rèn)為是動(dòng)態(tài)規(guī)劃算法的一個(gè)特例洪燥，相比動(dòng)態(tài)規(guī)劃轻姿，使用貪心算法需要滿足更多的條件（貪心選擇性質(zhì)），但是效率比動(dòng)態(tài)規(guī)劃要高袱蜡。
比如說(shuō)一個(gè)算法問(wèn)題使用暴力解法需要指數(shù)級(jí)時(shí)間丝蹭，如果能使用動(dòng)態(tài)規(guī)劃消除重疊子問(wèn)題，就可以降到多項(xiàng)式級(jí)別的時(shí)間坪蚁，如果滿足貪心選擇性質(zhì)奔穿，那么可以進(jìn)一步降低時(shí)間復(fù)雜度，達(dá)到線性級(jí)別的敏晤。
什么是貪心選擇性質(zhì)呢?
簡(jiǎn)單說(shuō)就是：每一步都做出一個(gè)局部最優(yōu)的選擇贱田，最終的結(jié)果就是全局最優(yōu)。注意哦茵典，這是一種特殊性質(zhì)湘换，其實(shí)只有一部分問(wèn)題擁有這個(gè)性質(zhì)。
比如你面前放著 100 張人民幣统阿，你只能拿十張彩倚，怎么才能拿最多的面額？顯然每次選擇剩下鈔票中面值最大的一張扶平，最后你的選擇一定是最優(yōu)的帆离。
然而，大部分問(wèn)題明顯不具有貪心選擇性質(zhì)结澄。比如打斗地主哥谷，對(duì)手出對(duì)兒三，按照貪心策略麻献，你應(yīng)該出盡可能小的牌剛好壓制住對(duì)方们妥，但現(xiàn)實(shí)情況我們甚至可能會(huì)出王炸。這種情況就不能用貪心算法勉吻，而得使用動(dòng)態(tài)規(guī)劃解決监婶，參見(jiàn)「動(dòng)態(tài)規(guī)劃解決博弈問(wèn)題」。
一齿桃、概念
很經(jīng)典的貪心算法問(wèn)題 Interval Scheduling（區(qū)間調(diào)度問(wèn)題）惑惶。
給很多形如 [start, end] 的閉區(qū)間，算出這些區(qū)間中最多有幾個(gè)互不相交的區(qū)間短纵。
本質(zhì)是求這些時(shí)間區(qū)間的最大不相交子集带污。
二、貪心解法
正確的思路可以分為以下三步：
1香到、從區(qū)間集合 intvs 中選擇一個(gè)區(qū)間 x鱼冀，這個(gè) x 是在當(dāng)前所有區(qū)間中結(jié)束最早的（end 最斜ㄆ啤）。
2雷绢、把所有與 x 區(qū)間相交的區(qū)間從區(qū)間集合 intvs 中刪除泛烙。
3、重復(fù)步驟 1 和 2翘紊，直到 intvs 為空為止蔽氨。之前選出的那些 x 就是最大不相交子集。
步驟1可以按每個(gè)區(qū)間的 end 數(shù)值升序排序帆疟。所有與 x 相交的區(qū)間必然會(huì)與 x 的 end 相交鹉究；如果一個(gè)區(qū)間不想與 x 的 end 相交，它的 start 必須要大于（或等于）x 的 end踪宠。
public int intervalSchedule(int[][] intvs) {
if (intvs.length == 0) return 0;
// 按 end 升序排序
Arrays.sort(intvs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
// 至少有一個(gè)區(qū)間不相交
int count = 1;
// 排序后自赔，第一個(gè)區(qū)間就是 x
int x_end = intvs[0][1];
for (int[] interval : intvs) {
int start = interval[0];
if (start >= x_end) {
// 找到下一個(gè)選擇的區(qū)間了
count++;
x_end = interval[1];
}
}
return count;
}
三、Leetcode題目
435柳琢、無(wú)重疊區(qū)間
452绍妨、用最少數(shù)量的箭引爆氣球
