貪心算法介紹（Greedy Algorithm）

1. 貪心算法概念簡介

? 貪心算法Greedy Algorithm是一種在每一步選擇中都采取當(dāng)前狀態(tài)下最優(yōu)（或最有利）決策的算法策略，以期望通過這樣的局部最優(yōu)決策達(dá)到全局最優(yōu)解。它適用于那些具有最優(yōu)子結(jié)構(gòu)的問題，即問題的最優(yōu)解包含其子問題的最優(yōu)解。貪心算法的關(guān)鍵在于它做出的選擇是不可逆的，一旦選擇了某個選項，就不會再回溯考慮其他選項。

• 通過示例來感受貪心算法的思想

有一堆不同大小的餅干，大小分別為 1, 3, 2, 4, 5。而面前有一群孩子，胃口也不一樣。每個孩子的胃口代表了他們最小能接受的餅干大小，比如說，有的孩子最少要吃一個大小為 3 的餅干才能滿足。

目標(biāo)是盡可能多地滿足孩子們的胃口。

餅干大小：3, 2, 1, 4, 5

孩子胃口：3, 2, 4

• 貪心算法的過程

1. 排序：將餅干和孩子的胃口從小到大排序。

   • 餅干：1, 2, 3, 4, 5
   • 孩子：2, 3, 4

2. 逐步計算選擇最小的滿足：

   • 第一個孩子胃口為 2，直接選擇大小為 2 的餅干滿足他。
   • 第二個孩子胃口為 3，直接選擇大小為 3 的餅干滿足他。
   • 第三個孩子胃口為 4，直接選擇大小為 4 的餅干滿足他。

3. 結(jié)果：你成功地滿足了 3 個孩子。貪心算法通過每一步都做出當(dāng)前看起來最好的選擇（用最小的餅干去滿足最小的胃口），得出了一個不錯的結(jié)果。

使用非貪心算法的思維來解決的方式

• 動態(tài)規(guī)劃的過程（非貪心算法）

1. 狀態(tài)定義：

   • 創(chuàng)建一個二維數(shù)組 dp[i][j]，表示用前 i 個餅干去滿足前 j 個孩子能達(dá)到的最大滿足數(shù)。

2. 初始化：

   • dp[0][0] = 0 表示沒有餅干和沒有孩子時，滿足的孩子數(shù)為 0。

3. 狀態(tài)轉(zhuǎn)移：

   • 當(dāng)不使用當(dāng)前餅干：dp[i][j] = dp[i-1][j]
   • 當(dāng)使用當(dāng)前餅干（前提是餅干大小滿足孩子的胃口）：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + 1)

4. 逐步計算：

   • 用第一個餅干（大小為 1），不能滿足任何孩子，所以 dp[1][j] = 0 對于所有 j。
   • 用第二個餅干（大小為 2），可以滿足第一個孩子，更新 dp[2][1] = 1。
   • 用第三個餅干（大小為 3），可以滿足第二個孩子，更新 dp[3][2] = 2。
   • 用第四個餅干（大小為 4），可以滿足第三個孩子，更新 dp[4][3] = 3。
   • 用第五個餅干（大小為 5），沒有其他孩子可以滿足，但可以繼續(xù)保持 dp[5][3] = 3。

5. 結(jié)果：最終，dp[5][3] = 3 表示最多可以滿足 3 個孩子。

• 對比分析

  • 貪心算法：

    • 思路：每一步選擇當(dāng)前最優(yōu)解，不考慮未來可能性。
    • 優(yōu)點：計算速度快，適合簡單或可以局部最優(yōu)逼近全局最優(yōu)的問題。
    • 結(jié)果：在這個例子中，貪心算法直接選擇合適的餅干來滿足每個孩子，最終結(jié)果為 3 個孩子滿足。

  • 動態(tài)規(guī)劃：

    • 思路：通過記錄之前的計算結(jié)果，考慮所有可能的情況來構(gòu)建全局最優(yōu)解。
    • 優(yōu)點：能夠找到全局最優(yōu)解，適合復(fù)雜問題。
    • 結(jié)果：動態(tài)規(guī)劃考慮了所有可能的分配方式，得到了最大可能的 3 個孩子滿足。

雖然在這個例子中，貪心算法和動態(tài)規(guī)劃的結(jié)果相同，但貪心算法只在局部做出最優(yōu)選擇，不保證全局最優(yōu)。而動態(tài)規(guī)劃通過全面分析，確保找到了全局最優(yōu)解。動態(tài)規(guī)劃的計算更復(fù)雜，但適用于需要全局最優(yōu)解的問題。

2. 貪心算法的特點

1. 貪心選擇性質(zhì)：

   • 貪心算法在每一步都做出當(dāng)前看起來最優(yōu)的選擇，而不考慮這個選擇對未來步驟的影響。這種選擇是基于問題的貪心選擇性質(zhì)，即問題具有這樣的結(jié)構(gòu)：局部最優(yōu)選擇可以導(dǎo)致全局最優(yōu)解。

2. 無回溯：

   • 與動態(tài)規(guī)劃等其他算法不同，貪心算法做出選擇后不會回溯。這意味著一旦做出了一個貪心選擇，算法就會繼續(xù)前進(jìn)，即使這個選擇在后來看起來可能不是最佳選擇。

     貪心算法的不回溯特性強(qiáng)調(diào)了算法的確定性和一次性，每次選擇都是最終的，不依賴于未來的信息，也不考慮撤銷或修改之前的選擇。這種特性使得貪心算法在某些問題上非常高效，但在其他問題上可能需要更復(fù)雜的算法來確保找到全局最優(yōu)解。

3. 子問題局部最優(yōu)：

   • 貪心算法通常用于具有最優(yōu)子結(jié)構(gòu)的問題，即一個問題的最優(yōu)解包含其子問題的最優(yōu)解。這種特性允許算法在構(gòu)建解決方案的過程中，利用子問題的局部最優(yōu)解。

4. 簡單高效：

   • 貪心算法通常易于理解和實現(xiàn)，因為它的決策過程直觀且不需要復(fù)雜的優(yōu)化過程。此外，由于貪心算法不需要存儲所有可能的解決方案，因此它在空間復(fù)雜度上通常很低。

5. 不保證全局最優(yōu)：

   • 盡管貪心算法在某些問題上能夠找到全局最優(yōu)解，但它并不保證在所有情況下都能找到。這取決于問題本身是否滿足貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。

3. 貪心算法的應(yīng)用場景

• 物流優(yōu)化：在物流配送中，使用貪心算法來規(guī)劃最短或最快路徑，例如快遞員的包裹派送順序，以減少行駛距離和時間 。

貪心算法在物流優(yōu)化中的應(yīng)用主要體現(xiàn)在配送路徑的選擇上。其核心原理是每一步都選擇當(dāng)前狀態(tài)下的最優(yōu)決策，以期望最終得到全局的最優(yōu)解。在物流配送系統(tǒng)中，這通常意味著選擇最短或成本最低的配送路徑，以達(dá)到節(jié)省時間和成本的目的。

具體來說，貪心算法在物流配送中的優(yōu)化原理可以這樣理解：假設(shè)一個快遞員需要配送多個包裹到不同的地點，使用貪心算法，快遞員會先選擇最近的一個配送點進(jìn)行配送，完成后再選擇下一個最近的點，依此類推，直到所有的配送任務(wù)完成。這種方法簡單快捷，能夠快速得到一個近似的最優(yōu)解，盡管這個解可能不是絕對最優(yōu)的 。

• 網(wǎng)絡(luò)路由選擇：在計算機(jī)網(wǎng)絡(luò)中，通過貪心算法選擇數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑，例如OSPF（開放最短路徑優(yōu)先）協(xié)議 。

貪心算法在網(wǎng)絡(luò)路由選擇中的應(yīng)用主要是基于其局部最優(yōu)策略來實現(xiàn)快速決策。在網(wǎng)絡(luò)路由選擇中，貪心算法可以幫助路由器選擇到目的地的最短路徑或者成本最低的路徑。其基本原理是，在每個決策點上，路由器會根據(jù)當(dāng)前可用的信息，選擇一條看似最優(yōu)的路徑，而不考慮這條路徑對后續(xù)路由選擇的影響 。

在實際的網(wǎng)絡(luò)協(xié)議中，OSPF（Open Shortest Path First）是一個廣泛應(yīng)用的鏈路狀態(tài)路由協(xié)議，它使用Dijkstra算法來計算最短路徑樹，從而確定到達(dá)每個目的地的最佳路徑 。OSPF協(xié)議能夠快速響應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?#xff0c;并且計算出的路由路徑較為優(yōu)化 。

貪心算法并不總是能夠得到全局最優(yōu)解。在某些情況下，例如在存在環(huán)路或者路徑成本突然增加的場景下，貪心算法可能會陷入次優(yōu)解。因此，在設(shè)計路由算法時，需要考慮網(wǎng)絡(luò)的具體特點和需求，結(jié)合其他算法或機(jī)制來確保路由的穩(wěn)定性和效率

• 任務(wù)調(diào)度：在計算機(jī)系統(tǒng)中，貪心算法用于CPU任務(wù)調(diào)度，選擇優(yōu)先級最高或最早截止時間的任務(wù)先執(zhí)行 。

貪心算法在任務(wù)調(diào)度領(lǐng)域的應(yīng)用原理是選擇當(dāng)前最優(yōu)的任務(wù)進(jìn)行執(zhí)行，以期望通過局部最優(yōu)選擇累積達(dá)到全局的優(yōu)化目標(biāo)。這種策略通常涉及對任務(wù)列表按照特定標(biāo)準(zhǔn)（如最短執(zhí)行時間、最晚截止時間或最高優(yōu)先級）進(jìn)行排序，然后依次考慮每個任務(wù)，根據(jù)當(dāng)前資源狀態(tài)和約束條件決定是否執(zhí)行該任務(wù)。貪心算法的決策過程是即時的，不涉及對過去選擇的回溯，這使得算法在很多情況下能夠快速得到一個可行的解決方案，盡管這不一定是絕對最優(yōu)的。

• 數(shù)據(jù)壓縮：霍夫曼編碼是一種使用貪心算法的數(shù)據(jù)壓縮技術(shù)，通過為頻繁出現(xiàn)的字符分配較短的編碼來優(yōu)化存儲空間 。

貪心算法在數(shù)據(jù)壓縮中的應(yīng)用主要是通過霍夫曼編碼（Huffman Coding）實現(xiàn)的。霍夫曼編碼是一種非常有效的數(shù)據(jù)壓縮技術(shù)，它利用了貪心算法來為數(shù)據(jù)中的每個字符分配一個變長的編碼，其中出現(xiàn)頻率高的字符被分配較短的編碼，而出現(xiàn)頻率低的字符被分配較長的編碼，從而實現(xiàn)整體數(shù)據(jù)的壓縮 。

霍夫曼編碼的實現(xiàn)原理基于構(gòu)建一棵霍夫曼樹，這棵樹是通過一個由字符出現(xiàn)頻率決定的優(yōu)先隊列構(gòu)建的。算法從隊列中取出頻率最小的兩個節(jié)點，將它們合并為一個新節(jié)點，新節(jié)點的頻率是這兩個節(jié)點頻率之和，這個過程不斷重復(fù)，直到隊列中只剩下一個節(jié)點，這個節(jié)點就是霍夫曼樹的根節(jié)點 。

在構(gòu)建霍夫曼樹的過程中，樹中的每個左節(jié)點對應(yīng)一個’0’編碼，每個右節(jié)點對應(yīng)一個’1’編碼。從根節(jié)點到葉節(jié)點的路徑就形成了字符的霍夫曼編碼。由于霍夫曼編碼要求任何編碼都不是其他編碼的前綴，這樣可以保證解碼時不會出現(xiàn)歧義 。

使用霍夫曼編碼進(jìn)行數(shù)據(jù)壓縮的過程可以顯著減少數(shù)據(jù)的存儲空間，壓縮率通常在20%到90%之間，這取決于數(shù)據(jù)的特性?；舴蚵幋a不僅考察了文本中不同字符的數(shù)量，還考慮了每個字符出現(xiàn)的頻率，通過這種方式，霍夫曼編碼實現(xiàn)了數(shù)據(jù)的有效壓縮

• 股票交易分析：在金融領(lǐng)域，貪心算法可以用來模擬股票買賣，選擇最優(yōu)的買入和賣出時機(jī)以最大化利潤 。

貪心算法在股票交易策略中的應(yīng)用是利用局部最優(yōu)決策來實現(xiàn)利潤最大化。它通過跟蹤股票價格變動，在價格低點買入并在高點賣出，以此累積利潤。同時，算法會考慮交易成本如手續(xù)費，并適應(yīng)市場規(guī)則，例如交易冷凍期和交易次數(shù)限制。貪心算法的實現(xiàn)簡單高效，適合快速變化的股票市場，盡管它不保證全局最優(yōu)，但通常能夠獲得接近最優(yōu)的交易結(jié)果。

• 廣告投放：在廣告行業(yè)，通過貪心算法優(yōu)化廣告投放策略，選擇最有效的廣告組合和展示順序以吸引用戶 。

貪心算法在廣告投放領(lǐng)域的應(yīng)用主要體現(xiàn)在對廣告展示機(jī)會的優(yōu)化分配上。具體來說，廣告系統(tǒng)需要在多個廣告主的合約中做出選擇，以確保每個廣告主都能獲得合約中規(guī)定的曝光量，同時還要考慮到曝光的時間分布，避免廣告在短期內(nèi)過度集中展示 。這種分配問題可以視為一個優(yōu)化問題，其中貪心算法因其簡單高效的特性而被廣泛應(yīng)用。

在廣告投放中，貪心算法的一個典型應(yīng)用是解決合約制廣告的在線分配問題。這類問題通常涉及到大量的廣告主合約和流量，算法需要在保證所有合約完成的同時，盡可能地滿足廣告主對曝光量和時間分布的要求。貪心算法通過在每次曝光機(jī)會出現(xiàn)時，選擇當(dāng)前最優(yōu)的廣告主進(jìn)行展示，從而實現(xiàn)對廣告流量的動態(tài)分配 。

貪心算法還可以用于處理廣告投放中的其他優(yōu)化問題，如廣告位的分配、廣告內(nèi)容的個性化推薦等。在這些場景中，貪心算法通過在每一步選擇中采取當(dāng)前最優(yōu)的決策，以達(dá)到整體的優(yōu)化目標(biāo)

4. 貪心算法的優(yōu)缺點

• 優(yōu)點

1. 簡單高效：貪心算法通常易于理解和實現(xiàn)，執(zhí)行速度快，不需要復(fù)雜的優(yōu)化過程。
2. 快速得到解決方案：貪心算法能夠迅速給出問題的解決方案，對于需要即時決策的問題特別有用。
3. 空間效率高：由于其決策過程不需要存儲所有可能的解決方案，因此空間復(fù)雜度通常較低。
4. 適應(yīng)性廣：貪心算法可以應(yīng)用于多種問題領(lǐng)域，如資源分配、路徑選擇、任務(wù)調(diào)度等。
5. 啟發(fā)式方法：作為一種啟發(fā)式算法，貪心算法用于快速找到一個可接受的解決方案，而不是總是尋找最優(yōu)解。

• 缺點

1. 不保證全局最優(yōu)：貪心算法在某些情況下可能無法得到全局最優(yōu)解，特別是當(dāng)問題不具有貪心選擇性質(zhì)時。
2. 依賴于問題結(jié)構(gòu)：貪心算法的成功依賴于問題是否具有最優(yōu)子結(jié)構(gòu)，對于不具備這種結(jié)構(gòu)的問題可能不適用。
3. 可能錯過更優(yōu)解：由于貪心算法的決策是不可逆的，一旦做出選擇就不再回溯，可能會錯過更優(yōu)的解決方案。
4. 局限性：對于一些NP難問題，貪心算法可能只能得到局部最優(yōu)解，而不是絕對最優(yōu)解。
5. 需要問題證明：在使用貪心算法時，需要證明其正確性，這可能需要一些數(shù)學(xué)推理和證明工作。

5. 貪心算法的實現(xiàn)步驟

1. 明確問題：

   • 確定你要解決的問題是什么，比如分配資源、選擇任務(wù)、規(guī)劃路徑等。

2. 理解貪心選擇：

   • 找出問題中可以應(yīng)用貪心選擇的地方，即在每一步選擇中都采取當(dāng)前看起來最好的決策。

3. 設(shè)定目標(biāo)：

   • 確定你的“貪心目標(biāo)”是什么，也就是你希望通過貪心選擇達(dá)到什么樣的效果，比如最小化成本、最大化利潤等。

4. 準(zhǔn)備數(shù)據(jù)：

   • 收集并準(zhǔn)備所有需要的數(shù)據(jù)，比如資源數(shù)量、任務(wù)列表、路徑信息等。

5. 排序或組織數(shù)據(jù)：

   • 根據(jù)你的目標(biāo)，可能需要對數(shù)據(jù)進(jìn)行排序或以某種方式組織，以便貪心選擇可以更容易進(jìn)行。

6. 執(zhí)行貪心策略：

   • 從第一步開始，每次都選擇當(dāng)前看起來最佳的選項。例如，如果你的目標(biāo)是最小化成本，那么就選擇成本最低的選項。

7. 更新選擇狀態(tài)：

   • 每次做出選擇后，更新當(dāng)前的狀態(tài)，這可能意味著從可用選項中移除已選擇的選項，或者更新剩余資源的數(shù)量。

8. 重復(fù)選擇過程：

   • 繼續(xù)執(zhí)行貪心選擇，直到所有的選項都被選擇完，或者達(dá)到某個特定的條件。

9. 檢查結(jié)果：

   • 完成所有步驟后，檢查你的結(jié)果是否滿足問題的要求。

10. 評估和調(diào)整：

    • 如果結(jié)果不是預(yù)期的，可能需要回到前面的步驟，調(diào)整你的貪心策略或選擇標(biāo)準(zhǔn)。

舉個例子，如果要用貪心算法來安排一天的工作，步驟可能是這樣的：

• 確定你要完成的所有工作任務(wù)。
• 決定你的貪心目標(biāo)，比如完成最多的任務(wù)或完成最重要的任務(wù)。
• 列出每個任務(wù)需要的時間和重要性。
• 根據(jù)任務(wù)的緊急程度或重要性對任務(wù)進(jìn)行排序。
• 從列表的頂部開始，逐個選擇任務(wù)，并安排到你的日程中。
• 每次選擇后，更新你的日程表，直到所有任務(wù)都被安排或時間被填滿。
• 最后，檢查你的日程表，確保所有任務(wù)都已妥善安排。

6. 貪心算法與其他算法的比較

特征/算法類型	貪心算法	分治算法	動態(tài)規(guī)劃	回溯算法	其他算法（如分支限界法）
基本思想	每一步都采取當(dāng)前最優(yōu)解	將原問題分解為子問題	解決子問題后合并結(jié)果	通過試錯嘗試所有可能	系統(tǒng)性搜索解空間，使用界限剪枝
適用問題	具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)的問題	具有最優(yōu)子結(jié)構(gòu)且子問題相互獨立	具有重疊子問題且最優(yōu)子結(jié)構(gòu)	需要遍歷所有可能解的問題	求解目標(biāo)明確的最優(yōu)化問題
子問題結(jié)構(gòu)	只有一個子問題	子問題相互獨立	子問題重疊，可能有多個解	所有可能的子問題組合	逐步細(xì)化問題的解空間
求解策略	先選擇后解決問題	分解問題后遞歸求解	自底向上，先求解子問題	逐步構(gòu)造解，剪枝無效選項	逐步搜索并剪枝非最優(yōu)解
時間效率	高效，通常時間復(fù)雜度較低	高效，但可能需要重復(fù)計算	可能較高，但利用記憶化減少重復(fù)計算	可能較低，尤其是解空間大時	高效性取決于剪枝策略
空間效率	通常較低，不需要存儲所有子問題	較低，遞歸調(diào)用可能增加空間消耗	可能較高，需要存儲子問題解	較高，需要回溯所有路徑	空間效率取決于界限剪枝的效果
優(yōu)點	簡潔高效，實現(xiàn)簡單	適用于獨立子問題，易于并行處理	能解決具有重疊子問題的復(fù)雜問題	能找到所有解，適用于組合問題	系統(tǒng)性搜索，避免無效搜索
缺點	可能無法得到全局最優(yōu)解	對子問題的獨立性要求較高	空間消耗大，狀態(tài)空間可能很大	對于大規(guī)模問題效率較低	可能需要較多的計算資源進(jìn)行剪枝
典型應(yīng)用	貨幣找零、霍夫曼編碼	快速排序、歸并排序	背包問題、最短路徑問題	數(shù)獨游戲、八皇后問題	旅行商問題、車輛路徑問題

7. 貪心算法的示例演示

示例1：分糖果問題

簡介：有一組孩子的胃口值 g 和一組糖果的大小 s，我們要盡量多的滿足孩子。每個孩子只能拿到一個糖果，且只有當(dāng)糖果的大小大于或等于孩子的胃口值時，孩子才能滿足。

思維過程：

1. 目標(biāo)：最大化能滿足的孩子數(shù)量。
2. 貪心選擇：每次優(yōu)先滿足胃口最小的孩子，因為大胃口的孩子可以用大糖果來滿足，但小胃口的孩子需要較小的糖果。
3. 步驟分析：
   • 首先對孩子的胃口和糖果的大小進(jìn)行排序，以便從最小的胃口和最小的糖果開始比較。
   • 然后，逐一遍歷糖果，嘗試將糖果分給胃口最小的孩子。
   • 如果糖果能夠滿足當(dāng)前孩子，就給這個孩子糖果，并繼續(xù)考慮下一個孩子。
   • 最后，統(tǒng)計并返回能夠滿足的孩子數(shù)量。

def findContentChildren(g, s):# 對孩子的胃口和糖果大小進(jìn)行排序g.sort()s.sort()# 用于統(tǒng)計能夠滿足的孩子數(shù)量child_i = 0# 遍歷每個糖果的大小for size in s:# 如果當(dāng)前孩子的胃口能被滿足if child_i < len(g) and size >= g[child_i]:child_i += 1  # 孩子得到了糖果# 返回能夠滿足的孩子數(shù)量return child_i# 測試
g = [1, 2, 5, 4, 3, 666]  # 孩子的胃口值
s = [1, 2, 1, 1]  # 糖果的大小
print(findContentChildren(g, s))  # 輸出: 2

胃口 g = [1, 2, 5, 4, 3, 666] 排序 -> [1, 2, 3, 4, 5, 666]

糖果 s = [1, 2, 1, 1] 排序 -> [1, 1, 1, 2]

糖果s[1]->g[1] +1

糖果s[1 ,1] -> g[2] +1

剩下糖果不滿足于孩子的胃口值，通過貪心算法，我們總是優(yōu)先滿足胃口最小的孩子，這樣能使得最多的孩子得到糖果

示例2：零錢兌換問題

簡介：給定一些硬幣面值 coins 和一個目標(biāo)金額 amount，找到能夠湊成該金額的最少硬幣數(shù)。

思維過程：

1. 目標(biāo)：最小化使用的硬幣數(shù)量。
2. 貪心選擇：每次選擇面值最大的硬幣，這樣可以盡快減少剩余的金額，減少所需的硬幣數(shù)量。
3. 步驟分析：
   • 將硬幣按面值從大到小排序，以便優(yōu)先使用大面值的硬幣。
   • 依次從最大的硬幣開始，計算該硬幣可以使用多少次，減少目標(biāo)金額。
   • 剩余金額用更小面值的硬幣繼續(xù)湊。
   • 最后，如果能完全湊成目標(biāo)金額，就返回硬幣數(shù)量；否則返回 -1。

def coinChange(coins, amount):# 將硬幣面值從大到小排序coins.sort(reverse=True)count = 0  # 統(tǒng)計使用的硬幣數(shù)量# 遍歷每種面值的硬幣for coin in coins:if amount == 0:  # 如果金額已經(jīng)為0，停止breakcount += amount // coin  # 使用最大面值硬幣的最大數(shù)量amount %= coin  # 更新剩余金額# 如果金額能夠被完全兌換，返回硬幣數(shù)量，否則返回-1return count if amount == 0 else -1# 測試
coins = [1, 2, 5]  # 硬幣面值
amount = 11  # 目標(biāo)金額
print(coinChange(coins, amount))  # 輸出: 3

通過每次選擇最大的硬幣，我們可以盡快減少目標(biāo)金額，達(dá)到使用最少硬幣的目的。

11->(5,5,1)

示例3：區(qū)間調(diào)度問題

簡介：給定一組時間區(qū)間 intervals，找出最多的互不重疊的區(qū)間數(shù)。例如，多個會議時間重疊的情況下，最多能夠安排多少場不沖突的會議。

思維過程：

1. 目標(biāo)：最大化選擇的區(qū)間數(shù)量。
2. 貪心選擇：每次選擇結(jié)束時間最早且與前一個區(qū)間不重疊的區(qū)間，這樣可以給后續(xù)的區(qū)間留出更多的時間。
3. 步驟分析：
   • 首先按區(qū)間的結(jié)束時間進(jìn)行排序，以便優(yōu)先考慮結(jié)束時間早的區(qū)間。
   • 從第一個區(qū)間開始，選擇它作為第一個非重疊區(qū)間，并記錄它的結(jié)束時間。
   • 依次考慮后續(xù)的區(qū)間，如果它的開始時間不早于前一個區(qū)間的結(jié)束時間，就選擇這個區(qū)間，并更新結(jié)束時間。
   • 最后，返回選擇的區(qū)間數(shù)量。

def intervalSchedule(intervals):# 根據(jù)區(qū)間的結(jié)束時間進(jìn)行排序intervals.sort(key=lambda x: x[1])count = 0  # 統(tǒng)計能夠安排的區(qū)間數(shù)量end = float('-inf')  # 記錄上一個選擇的區(qū)間的結(jié)束時間# 遍歷所有區(qū)間for interval in intervals:if interval[0] >= end:  # 如果當(dāng)前區(qū)間的開始時間大于等于上一個區(qū)間的結(jié)束時間count += 1  # 選擇當(dāng)前區(qū)間end = interval[1]  # 更新結(jié)束時間# 返回能夠安排的最大區(qū)間數(shù)量return count# 測試
intervals = [[1, 3], [2, 4], [3, 5]]  # 時間區(qū)間
print(intervalSchedule(intervals))  # 輸出: 2

通過每次選擇結(jié)束時間最早的區(qū)間，能夠留下更多的時間給后面的區(qū)間，從而選擇盡可能多的

[1, 3], [2, 4]區(qū)間重疊, [3, 5] -> [1, 3], [3, 5] -> 2

示例4：分配會議室問題

簡介：給定一組會議的開始和結(jié)束時間intervals，找出需要的最少會議室數(shù)量，以確保所有會議都能安排上。

思維過程：

1. 目標(biāo)：最小化同時進(jìn)行的會議數(shù)（即需要的會議室數(shù)）。
2. 貪心選擇：每次安排一個會議時，檢查最早結(jié)束的會議是否已經(jīng)結(jié)束，如果結(jié)束了就可以復(fù)用該會議室，否則需要新開一個會議室。
3. 步驟分析：
   • 先將所有會議按開始時間排序。
   • 使用一個最小堆來跟蹤當(dāng)前所有正在進(jìn)行的會議的結(jié)束時間。
   • 對于每個會議，如果它的開始時間不早于最早結(jié)束的會議的結(jié)束時間，則表示可以復(fù)用一個會議室，更新堆中的結(jié)束時間。
   • 否則，需要新開一個會議室，將會議的結(jié)束時間加入堆中。
   • 最后，堆的大小就是需要的最少會議室數(shù)量。

import heapqdef minMeetingRooms(intervals):if not intervals:return 0# 根據(jù)會議的開始時間進(jìn)行排序intervals.sort(key=lambda x: x[0])# 初始化一個最小堆，用于存儲當(dāng)前進(jìn)行的會議的結(jié)束時間heap = []heapq.heappush(heap, intervals[0][1])  # 將第一個會議的結(jié)束時間加入堆中# 遍歷剩余的會議for i in intervals[1:]:# 如果當(dāng)前會議的開始時間大于等于堆頂?shù)慕Y(jié)束時間if i[0] >= heap[0]:heapq.heappop(heap)  # 移除堆頂?shù)臅h，因為它已經(jīng)結(jié)束了heapq.heappush(heap, i[1])  # 將當(dāng)前會議的結(jié)束時間加入堆中# 最后堆的大小就是需要的會議室數(shù)量return len(heap)# 測試
intervals = [[0, 30], [5, 10], [15, 20], [5, 20], [35, 40]]  # 會議時間區(qū)間
print(minMeetingRooms(intervals))  # 輸出: 3

使用最小堆動態(tài)管理會議的結(jié)束時間，通過貪心選擇，及時釋放已結(jié)束的會議室，確保所需的會議室數(shù)量最少。

示例5：最大子數(shù)組和問題

簡介：在一個整數(shù)數(shù)組 nums 中，找到和最大的連續(xù)子數(shù)組，并返回其最大和。

思維過程：

1. 目標(biāo)：找到和最大的連續(xù)子數(shù)組。
2. 貪心選擇：每次都判斷是將當(dāng)前元素加入到之前的子數(shù)組中，還是重新開始一個新的子數(shù)組，從而保證當(dāng)前的子數(shù)組和盡可能大。
3. 步驟分析：
   • 初始化當(dāng)前子數(shù)組和 current_sum 和最大子數(shù)組和 max_sum 為第一個元素。
   • 從第二個元素開始，逐個判斷：
     • 當(dāng)前元素是否比 current_sum + 當(dāng)前元素 更大。如果是，則拋棄之前的子數(shù)組，重新開始；否則將當(dāng)前元素加入到當(dāng)前子數(shù)組中。
   • 每次更新最大子數(shù)組和 max_sum。
   • 最終返回最大子數(shù)組和。

def maxSubArray(nums):max_sum = nums[0]  # 初始化最大和為數(shù)組的第一個元素current_sum = nums[0]  # 當(dāng)前子數(shù)組的和# 遍歷數(shù)組的其余元素for num in nums[1:]:# 如果當(dāng)前子數(shù)組的和加上當(dāng)前元素還不如當(dāng)前元素本身大，就丟棄當(dāng)前子數(shù)組，重新開始current_sum = max(num, current_sum + num)# 更新最大和max_sum = max(max_sum, current_sum)# 返回最大子數(shù)組和return max_sum# 測試
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]  # 輸入數(shù)組
print(maxSubArray(nums))  # 輸出: 6

通過貪心策略，決定是否將當(dāng)前元素加入到之前的子數(shù)組中，從而保證當(dāng)前的子數(shù)組和盡可能大，最終找到全局最大子數(shù)組和。

8. 貪心算法的回顧總結(jié)

貪心算法是一種在每一步選擇中都采取當(dāng)前最優(yōu)解的策略，以期望構(gòu)建出全局最優(yōu)解的算法。它的核心思想是“貪心選擇性質(zhì)”，即在每個決策點上，基于當(dāng)前信息選擇最有利的選項，從而希望通過這些局部最優(yōu)決策累積成全局最優(yōu)解。貪心算法的實現(xiàn)通常簡單直接，易于編碼，且執(zhí)行效率高，這使得它在需要快速響應(yīng)的大規(guī)模問題中非常有用。

貪心算法的關(guān)鍵在于其貪心策略的選擇，這通常涉及到對問題結(jié)構(gòu)的深入理解。在某些問題中，貪心算法能夠保證找到最優(yōu)解，特別是當(dāng)問題具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)時。然而，并非所有問題都適合使用貪心算法，有些情況下貪心算法可能只能得到局部最優(yōu)解而非全局最優(yōu)解。

貪心算法的一個顯著特點是其決策過程是單向的，不會回溯。這意味著一旦做出選擇，算法不會重新考慮之前的決策，即使這些決策最終可能不是最佳選擇。這種特性使得貪心算法在時間效率上具有優(yōu)勢，但同時也限制了它在某些需要全局考慮的問題上的適用性。

貪心算法廣泛應(yīng)用于資源分配、路徑規(guī)劃、任務(wù)調(diào)度、數(shù)據(jù)壓縮等領(lǐng)域。例如，在霍夫曼編碼中用于數(shù)據(jù)壓縮，在Dijkstra算法中用于尋找單源最短路徑。盡管貪心算法在某些情況下可能需要結(jié)合其他算法來優(yōu)化其策略，但其作為一種高效且直觀的算法，仍然在算法設(shè)計和優(yōu)化問題解決中占有重要地位。