貪心算法

顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。
該算法存在問題：

①不能保證求得的最后解是最佳的；

②不能用來求最大或最小解問題；

③ 只能求滿足某些約束條件的可行解的范圍。

區(qū)間貪心

（1）區(qū)間相交
（2）區(qū)間不相交
（3）區(qū)間包含（特殊的區(qū)間相交）
2.解決的辦法
（1）當(dāng)區(qū)間包含時(shí)，我們只留小區(qū)間。
（2）然后我們將所有區(qū)間的左端點(diǎn)也就是 x 從大到小排序，然后每次找出右端點(diǎn)在這個(gè)左端點(diǎn)左面的就是一個(gè)，然后選取這個(gè)區(qū)間的左端點(diǎn)作為下次判斷的標(biāo)準(zhǔn)，當(dāng)左端點(diǎn)相同時(shí)，按照右端點(diǎn) y 從小到大排序，就是我們檢查時(shí)先檢查（左端點(diǎn)相同時(shí)）右端點(diǎn)小的（正好可以去去除區(qū)間包含的大區(qū)間）

首先明確一個(gè)問題：假設(shè)有兩個(gè)區(qū)間x,y，區(qū)間x完全包含y。那么，選x是不劃算的，因為x和y最多只能選一個(gè)，選x還不如選y，這樣不僅區(qū)間數(shù)目不會(huì)減少，而且給其他區(qū)間留出了更多的位置。接下來，按照bi從小到大的順序給區(qū)間排序。
貪心策略是：一定要選第一個(gè) 區(qū)間。

圖1
來看圖1中的區(qū)間1和區(qū)間2：
如果區(qū)間2和區(qū)間1完全不相交，那么沒有影響（因此一定要選區(qū)間1），否則區(qū)間1和區(qū)間2最多只能選一個(gè)。如果不選區(qū)間2，區(qū)間1的①部分其實(shí)是沒有任何影響的（它不會(huì)擋住任何一個(gè)區(qū)間），區(qū)間1的有效部分其實(shí)變成了②部分，它被區(qū)間2所包含！由剛才的結(jié)論，區(qū)間2是不能選的。依此類推，不能因?yàn)檫x任何區(qū)間而放棄區(qū)間1，因此選擇區(qū)間1是明智的。
選擇了區(qū)間1以后，需要把所有和區(qū)間1相交的區(qū)間排除在外，需要記錄上一個(gè)被選擇的區(qū)間編號(hào)。這樣，在排序后只需要掃描一次即可完成貪心過程，得到正確結(jié)果。

參考：