文章目錄
前言
一、什么是貪心算法？
貪心算法的基本概念：貪心算法并不從整體最優上加以考慮，所做的選擇只是在某種意義上的局部最優選擇。
二、會議安排題目
1.題目理解
2.思路剖析
總結
前言
本文將主要介紹貪心算法需要注意的地方以及基本概念，理解和解決最經典的會議安排問題，以及有相應的變形題
一、什么是貪心算法？
-
貪心算法的基本概念：貪心算法并不從整體最優上加以考慮，所做的選擇只是在某種意義上的局部最優選擇。
- 貪心算法的基本要素：
- 最優子結構性質：一個問題的最優解包含其子問題的最優解。
- ?貪心選擇性質：在每一步選擇中都采取當前狀態下的最優選擇，即不考慮未來的影響，僅考慮當前步的選擇，從而希望最終能夠找到全局最優解。
二、會議安排題目
1.題目理解
這里我們需要根據活動的開始和結束時間來安排最多的活動數目，前提是這里只有一個會場并且時間也只有一天，對于安排活動，根據日常的生活經驗，我們可以想到有下面三種安排方式：
- 先來先服務：誰開始的時間早就安排誰
- 最短作業時間優先：誰占用會場的時間少就先安排誰
- 截止時間優先：誰結束的早就先安排誰
下面我們來逐一分析：
如果采用第一種方式，第一個開始的活動占用了很長的時間就會導致后面的活動都無法安排，很多時候并不能滿足活動數最多
如果采用第二種方式，假如最晚開始的活動占用會場的時間最少，那么前面的時間都相當于浪費了，也不是一個好的選擇
而第三種方式根據結束時間的早晚來安排能夠最大程度的未為后面的活動騰出時間，故此類會議安排題目我們都是利用截止時間優先的方式進行安排
2.思路剖析
由上面的題目理解易知我們需要知道活動的開始時間、截止時間并且根據截止時間對活動進行排序。這里我們需要定義兩個數組 si 和 fi 分別存儲第 i 個活動的開始時間和截止時間，下面我們通過一個列題梳理代碼思路。
如圖所示，我們首先根據截止時間進行排序，然后我們選擇第一個活動最先開始，這時我們發現第一個活動的截止時間是7與第二個活動發生沖突（不相容）則我們要將這個活動去掉，再選擇開始時間大于第一個活動的截止時間的活動也就是第三個活動，同理安排好第三個活動，我們也要將沖突的活動剔除，依次類推我們可以選擇1、3、5或者1、3、6這兩種安排方式，通過這個例題也說明了貪心算法的最優解是不唯一的
下面是這個過程的核心代碼：
void GreedySelector(int n, int s[],int f[],bool A[]) { A[1]=true;//安排第一個活動int j=1;//當前結束活動的下標for(int i=2;i<=n;i++){if(s[i]>f[j]){A[i]=true;//將活動列入安排中j=i;//更新當前結束的活動}elseA[i]=false; }}
總結
本文通過貪心算法解決了經典的會議安排問題，即在有限的會議室資源下安排盡可能多的互不沖突的活動。首先，我們定義開始時間和結束時間兩個關鍵數組。然后采用貪心算法的策略，按照活動結束時間進行排序，確保每次選擇最早結束的活動，從而為后續活動留出更多時間。在具體實現中，使用標志數組來跟蹤已安排的活動，并通過迭代選擇兼容活動來完成最優安排。通過示例分析，我們驗證了該算法能夠正確計算出最多可安排的活動數量及其具體組合。這種基于貪心選擇的方法不僅保證了解決方案的最優性，還具有較高的執行效率（O(n log n)時間復雜度），非常適合處理此類活動調度問題。
喜歡的朋友們點贊支持一下啦~
)
