定義

貪心算法是指每一步都求最優解，迭代求得可能是全局最優解的算法。當然局部最優解可能不是全局最優解，也可能是全局最優解，這就要看選擇的貪心策略了。一般證明選擇的策略是正確的，可以使用數學歸納法來證明，一般證明較難，可以寫一個暴力的方式求得最優解，然后試不同的貪心策略，看哪一種正確即可，這個就是對數器的思路。

對數器就是通過大量的測試數據來驗證算法是否正確的方式。

對數器核心部件有兩個：

• 絕對正確的方法
• 能產生大量隨機樣例的隨機發生器

貪心算法舉例

開最多的會議

題目： 給定每一個會議開始的時間和結束的時間，怎么安排會議要求會

議室進行的會議的場次最多。返回這個最多的會議場次。

貪心策略：根據哪個項目早結束安排哪個

代碼：

總結

貪心算法，因為是要選一種局部最優解，要么選最大值，要么選最小值。所以基本上貪心算法都可以使用到堆的結構來解決。多做幾道貪心算法的題就有感覺了。