活動選擇問題
問題
你有一系列的事情要做（活動）。每個活動都有一個開始時間和一個結束時間。你不能一次執行多項活動。你的任務是找到一種方法來執行最大數量的活動。
例如，假設你有一系列可供選擇的類。
| 活動編號 | 開始時間 | 時間結束 |
|---|---|---|
1 |
上午 10 點 20 分 | 上午 11 時 |
2 |
上午 10:30 | 上午 11:30 |
3 |
上午 11 點 | 12.00 |
4 |
上午 10 點 | 上午 11:30 |
5 |
上午 9 點 | 上午 11 時 |
記住，你不能同時上兩節課。這意味著你不能上 1 級和 2 級，因為他們共享一個共同的時間 10.30 AM 到 11.00 AM 然而，你可以參加 1 級和 3 級，因為他們沒有共同的時間。因此，你的任務是儘可能獲取最大數量的類，而不會有任何重疊。你怎麼能這樣做？
分析
讓我們通過貪婪的方法來思考解決方案。首先，我們隨機選擇一些方法並檢查是否有效。
- **按開始時間對活動進行排序，**這意味著首先從哪個活動開始我們將首先採取它們。然後從排序列表中取第一個到最後一個並檢查它是否會與之前的活動相交。如果當前活動與之前採取的活動不相交，我們將執行活動，否則我們將無法執行。這種方法適用於某些情況
| 活動編號 | 開始時間 | 時間結束 |
|---|---|---|
1 |
上午 11 點 | 下午 1:30 |
2 |
上午 11:30 | 中午 12:00 |
3 |
下午 1 點 30 分 | 下午 2:00 |
4 |
上午 10 點 | 上午 11 時 |
排序順序為 4 - > 1 - > 2 - > 3.將執行活動 4 - > 1 - > 3，並跳過活動 2。將執行最多 3 項活動。它適用於此類情況。但在某些情況下會失敗。讓我們將這種方法應用於案例
| 活動編號 | 開始時間 | 時間結束 |
|---|---|---|
1 |
上午 11 點 | 下午 1:30 |
2 |
上午 11:30 | 中午 12:00 |
3 |
下午 1 點 30 分 | 下午 2:00 |
4 |
上午 10 點 | 下午 3:00 |
排序順序為 4 - > 1 - > 2 - > 3，僅執行活動 4，但答案可以是活動 1 - > 3 或 2 - > 3 將執行。因此，我們的方法不適用於上述情況。讓我們嘗試另一種方法
- **按持續時間對活動進行排序，**這意味著首先執行最短的活動。這可以解決以前的問題。雖然問題沒有完全解決。仍有一些案例可能導致解決方案失敗。在下面的案例中應用這種方法。
| 活動編號 | 開始時間 | 時間結束 |
|---|---|---|
1 |
早上 6 點 | 上午 11 點 40 分 |
2 |
上午 11:30 | 中午 12:00 |
3 |
晚上 11 點 40 分 | 下午 2:00 |
如果我們按持續時間對活動進行排序，則排序順序為 2 - > 3 —> 1。如果我們先進行 2 號活動，那麼就不能進行其他活動了。但答案是執行活動 1 然後執行 3。所以我們可以執行最多 2 個活動。所以這不能解決這個問題。我們應該嘗試不同的方法。
解決方案
- **通過結束時間對活動進行排序，**這意味著活動首先完成。演算法如下
- 按活動結束時間對活動進行排序。
- 如果要執行的活動與先前執行的活動不共享共同時間，請執行活動。
讓我們分析第一個例子
| 活動編號 | 開始時間 | 時間結束 |
|---|---|---|
1 |
上午 10 點 20 分 | 上午 11 時 |
2 |
上午 10:30 | 上午 11:30 |
3 |
上午 11 點 | 12.00 |
4 |
上午 10 點 | 上午 11:30 |
5 |
上午 9 點 | 上午 11 時 |
按結束時間對活動進行排序，因此排序順序為 1 - > 5 - > 2 - > 4 - > 3 ..答案為 1 - > 3 這兩項活動將被執行。這就是答案。這是 sudo 程式碼。
- 排序：活動
- 從排序的活動列表中執行第一個活動。
- 設定：Current_activity：=第一個活動
- set：end_time：=當前活動的 end_time
- 如果存在則轉到下一個活動，如果不存在則終止。
- 如果當前活動的 start_time <= end_time：執行活動並轉到 4
- 別的：得到 5。
請參閱此處獲取編碼幫助 http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/