在這個問題中，“有限的時間內（這段時間應該是連續的）”是其中的一個限制條件，也應該是有一個起始時間和一個結束時間（簡單化，起始時間可以是會議最早開始的時間，結束時間可以是會議最晚結束的時間），任務就是實現召開更多的滿足在這個“有限的時間內”等待安排的會議，如下圖所示：

從上圖可以看出，{會議1，會議4，會議6，會議8，會議9}，{會議2，會議4，會議7，會議8，會議9}都是能安排最多的會議集合。

要讓會議數最多，我們需要選擇最多的不相交時間段。我們可以嘗試貪心策略：

（1）每次從剩下未安排的會議中選擇會議具有最早開始時間且與已安排的會議相容的會議安排，以增大時間資源的利用率。
（2）每次從剩下未安排的會議中選擇持續時間最短且與已安排的會議相容的會議安排，這樣可以安排更多一些的會議。
（3）每次從剩下未安排的會議中選擇具有最早結束時間且與已安排的會議相容的會議安排，這樣可以儘快安排下一個會議。

思考一下，如果選擇最早開始時間，則如果會議持續時間很長，例如8點開始，卻要持續12個小時，這樣一天就只能安排一個會議；如果選擇持續時間最短，則可能開始時間很晚，例如19點開始，20點結束，這樣也只能安排一個會議，所以我們最好選擇那些開始時間要早，而且持續時間短的會議，即最早開始時間+持續時間最短，就是最早結束時間。

因此採用第（3）種貪心策略，每次從剩下的會議中選擇具有最早結束時間且與已安排的會議相容的會議安排。

2　算法設計

（1）初始化：將n個會議的開始時間、結束時間存放在結構體數組中（想一想，為什麼不用兩個一維數組分別存儲？），如果需要知道選中了哪些會議，還需要在結構體中增加會議編號，然後按結束時間從小到大排序（非遞減），結束時間相等時，按開始時間從大到小排序（非遞增）；

（2）根據貪心策略選擇第一個具有最早結束時間的會議，用last記錄剛選中會議的結束時間；

（3）選擇第一個會議之後，依次從剩下未安排的會議中選擇，如果會議i開始時間大於等於最後一個選中的會議的結束時間last，那麼會議i與已選中的會議相容，可以安排，更新last為剛選中會議的結束時間；否則，捨棄會議i，檢查下一個會議是否可以安排。

3 完美圖解

3.1 原始的會議時間表和排序後的會議時間表：

3.2 貪心選擇過程

（1）首先選擇排序後的第一個會議即最早結束的會議（編號為2），用last記錄最後一個被選中會議的結束時間，last=4。

（2）檢查餘下的會議，找到第一個開始時間大於等於 last（last=4）的會議，子問題轉化為從該會議開始，餘下的所有會議。如表3所示。

從子問題中，選擇第一個會議即最早結束的會議（編號為3），更新last為剛選中會議的結束時間last=7。

（3）檢查餘下的會議，找到第一個開始時間大於等於last（last=7）的會議，子問題轉化為從該會議開始，餘下的所有會議。如表4所示↑。

從子問題中，選擇第一個會議即最早結束的會議（編號為 7），更新 last 為剛選中會議的結束時間last=11。

（4）檢查餘下的會議，找到第一個開始時間大於等於last（last=11）的會議，子問題轉化為從該會議開始，餘下的所有會議。如表5所示。

從子問題中，選擇第一個會議即最早結束的會議（編號為10），更新last為剛選中會議的結束時間last=14；所有會議檢查完畢，算法結束。如表6所示↑。

3.4 構造最優解

從貪心選擇的結果，可以看出，被選中的會議編號為{2，3，7，10}，可以安排的會議數量最多為4，如表6所示↑。

4　重點代碼詳解

（1）數據結構定義

以下C++程序代碼中，結構體meet中定義了beg表示會議的開始時間，end表示會議的結束時間，會議meet的數據結構：

struct Meet
{
int beg; //會議的開始時間
int end; //會議的結束時間
} meet[1000]；

（2）對會議按照結束時間非遞減排序

我們採用C++中自帶的sort函數，自定義比較函數的辦法，實現會議排序，按結束時間從小到大排序（非遞減），結束時間相等時，按開始時間從大到小排序（非遞增）：

bool cmp(Meet x,Meet y)
{
if(x.end==y.end) //結束時間相等時
return x.beg>y.beg; //按開始時間從大到小排序
return x.end}
sort(meet,meet+n,cmp);

（3）會議安排問題的貪心算法求解

在會議按結束時間非遞減排序的基礎上，首先選中第一個會議，用last變量記錄剛剛被選中會議的結束時間。下一個會議的開始時間與last比較，如果大於等於last，則選中。每次選中一個會議，更新last為最後一個被選中會議的結束時間，被選中的會議數ans加1；如果會議的開始時間不大於等於last，繼續考查下一個會議，直到所有會議考查完畢。

上面介紹的程序中，只是返回了可以安排的會議最大數，而不知道安排了哪些會議，這顯然是不滿足需要的。我們可以改進一下，在會議結構體meet中添加會議編號num變量，選中會議時，顯示選中了第幾個會議。

5　編碼

輸入

輸入會議總數：
10
輸入會議的開始時間和結束時間，以空格分開：
8 10
9 11
10 15
11 14
13 16
14 17
15 17
17 18
18 20
16 19

輸出

排完序的會議時間如下：
會議編號 開始時間 結束時間
 1 8 10
 2 9 11
 4 11 14
 3 10 15
 5 13 16
 7 15 17
 6 14 17
 8 17 18
 10 16 19
 9 18 20
-------------------------------------------------
選擇的會議的過程：
 選擇第1個會議
 選擇第4個會議
 選擇第7個會議
 選擇第8個會議
 選擇第9個會議

使用上面貪心算法可得，選擇的會議是第2、3、7、10個會議，輸出最優值是4。

6　算法解析及優化拓展

6.1 算法複雜度分析

（1）時間複雜度：在該算法中，問題的規模就是會議總個數n。顯然，執行次數隨問題規模的增大而變化。首先在成員函數setMeet::init()中，輸入n個結構體數據。輸入作為基本語句，顯然，共執行n次。而後在調用成員函數setMeet::solve()中進行排序，易知sort排序函數的平均時間複雜度為O(nlogn)。隨後進行選擇會議，貢獻最大的為if(meet[i].beg>=last)語句，時間複雜度為O(n)，總時間複雜度為O(n +nlogn)= O(nlogn)。

（2）空間複雜度：在該算法中，meet[]結構體數組為輸入數據，不計算在空間複雜度內。輔助空間有i、n、ans等變量，則該程序空間複雜度為常數階，即O(1)。

6.2 算法優化拓展

想一想，你有沒有更好的辦法來處理此問題，比如有更小的算法時間複雜度？

參考：https://blog.csdn.net/rainchxy/article/details/77977910?utm_source=copy

附源代碼：

#include 
#include  

#include 
using namespace std;
struct Meet
{
 int beg;		//會議的開始時間
 int end;		//會議的結束時間
 int num;		//記錄會議的編號
}meet[1000];		//會議的最大個數為1000
 
class setMeet{
 public:
 void init();
 void solve();
 private:
 int n,ans;		// n:會議總數 ans: 最大的安排會議總數
};
 
//讀入數據
void setMeet::init()
{
 int s,e;
 cout < cin >> n;
 int i;
 cout < for(i=0;i {
 cin>>s>>e;
 meet[i].beg=s;
 meet[i].end=e;
 meet[i].num=i+1;
 }
}
 
bool cmp(Meet x,Meet y)
{
 if (x.end == y.end)
 return x.beg > y.beg;
 return x.end < y.end;
}
 
void setMeet::solve()
{
 sort(meet,meet+n,cmp);								//對會議按結束時間排序
 cout < int i;
 cout < for(i=0; i 
 {
 cout<< " " << meet[i].num< }
 cout < cout << "選擇的會議的過程：" < cout < ans=1;
 int last = meet[0].end;							//記錄剛剛被選中會議的結束時間
 for( i = 1;i < n;++i)
 {
 if(meet[i].beg>=last)
 {						//如果會議i開始時間大於等於最後一個選中的會議的結束時間
 ans++;
 last = meet[i].end;						//更新比較條件last
 cout < }
 }
 cout <}
 
int main()
{
 setMeet sm;
 sm.init();					//讀入數據
 sm.solve();					//貪心算法求解
 system("pause");
 return 0;
}

－End－