題目描述

問題背景

活動選擇問題是貪心算法的經典應用場景之一。假設有若干個活動，每個活動都有獨立的開始時間和結束時間，且同一時間只能進行一個活動。要求從這些活動中選擇出最大數量的不重疊活動，即任意兩個選中的活動，前一個活動的結束時間不晚于后一個活動的開始時間。

輸入輸出示例

• 輸入（開始時間與結束時間分兩行輸入，空格分隔，回車結束）：

  plaintext

  1 3 0 5 8 5  // 活動開始時間
  2 4 6 7 9 9  // 活動結束時間
  

• 輸出：

  plaintext

  最大不重疊活動數量: 4
  

• 解釋：最優選擇為活動?[1,2]、[3,4]、[5,7]、[8,9]，共 4 個不重疊活動。

解題思路：貪心算法的核心邏輯

為什么選擇貪心算法？

活動選擇問題的最優解具有 “貪心選擇性質”—— 每次選擇最早結束的活動，能為后續活動預留最多的時間，從而最大化最終選擇的活動數量。這一策略無需回溯，直接通過局部最優選擇即可得到全局最優解。

算法步驟

1. 數據組織：將每個活動的 “開始時間” 和 “結束時間” 組合成二維向量?vector<vector<int>>，每行代表一個活動（格式：[開始時間, 結束時間]）。
2. 排序：按活動的結束時間升序排序（貪心策略的關鍵，確保優先選擇早結束的活動）。
3. 篩選不重疊活動：
   • 初始選擇第一個活動（最早結束的活動），記錄其結束時間。
   • 遍歷后續活動，若當前活動的 “開始時間 ≥ 上一個選中活動的結束時間”，則選擇該活動，并更新結束時間。
4. 統計結果：記錄最終選擇的活動數量，即為答案。

完整 C++ 代碼實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;/*** @brief 計算最大不重疊活動數量（貪心算法）* @param activities 二維向量，每行存儲一個活動的[開始時間, 結束時間]*/
void selectMaxNonOverlappingActivities(vector<vector<int>>& activities) {// 邊界處理：若沒有活動，直接返回0if (activities.empty()) {cout << "最大不重疊活動數量: 0" << endl;return;}// 按活動結束時間升序排序（貪心算法核心：優先選早結束的活動）sort(activities.begin(), activities.end(), [](const vector<int>& activity1, const vector<int>& activity2) {return activity1[1] < activity2[1]; // 按結束時間從小到大排序});int activityCount = 1;                  // 至少選擇第一個活動int lastActivityEndTime = activities[0][1]; // 記錄上一個選中活動的結束時間// 遍歷剩余活動，篩選不重疊的活動for (size_t i = 1; i < activities.size(); ++i) {// 若當前活動的開始時間 ≥ 上一個活動的結束時間，說明不重疊if (activities[i][0] >= lastActivityEndTime) {activityCount++; // 選擇當前活動lastActivityEndTime = activities[i][1]; // 更新結束時間為當前活動的結束時間}}// 輸出結果cout << "最大不重疊活動數量: " << activityCount << endl;
}int main() {vector<int> startTimes;  // 存儲所有活動的開始時間vector<int> endTimes;    // 存儲所有活動的結束時間vector<vector<int>> activities; // 存儲所有活動（[開始時間, 結束時間]）int timeInput;           // 臨時存儲輸入的時間值// 讀取活動開始時間（空格分隔，回車結束）cout << "請輸入所有活動的開始時間（空格分隔，回車結束）：" << endl;while (cin >> timeInput) {startTimes.push_back(timeInput);// 檢測到回車符，停止讀取開始時間if (cin.peek() == '\n') {cin.ignore(); // 清空輸入緩沖區的換行符，避免影響后續輸入break;}}// 讀取活動結束時間（空格分隔，回車結束）cout << "請輸入所有活動的結束時間（空格分隔，回車結束）：" << endl;while (cin >> timeInput) {endTimes.push_back(timeInput);if (cin.peek() == '\n') {break;}}// 輸入合法性校驗：開始時間和結束時間的數量必須一致if (startTimes.size() != endTimes.size()) {cerr << "輸入錯誤：開始時間和結束時間的數量不匹配！" << endl;return 1; // 非0返回值表示程序異常退出}// 組合開始時間和結束時間，構建活動列表for (size_t i = 0; i < startTimes.size(); ++i) {activities.push_back({startTimes[i], endTimes[i]});}// 計算并輸出最大不重疊活動數量selectMaxNonOverlappingActivities(activities);return 0;
}

---

代碼細節解析

1. 邊界處理與輸入校驗

• 空活動判斷：若輸入為空（無任何活動），直接輸出 0，避免數組越界。
• 輸入合法性校驗：確保 “開始時間數量” 與 “結束時間數量” 一致，若不一致則提示錯誤并退出，避免后續邏輯異常。
• 輸入緩沖區清理：使用?cin.ignore()?清除第一個輸入后的換行符，防止換行符被第二個輸入循環誤讀。

2. 排序邏輯（Lambda 表達式）

cpp

運行

sort(activities.begin(), activities.end(), [](const vector<int>& activity1, const vector<int>& activity2) {return activity1[1] < activity2[1];});

• 使用 Lambda 表達式作為排序的自定義比較函數，簡潔高效。
• 按活動的結束時間（activity[1]）升序排序，是貪心策略的核心 —— 優先選擇早結束的活動，為后續活動預留更多時間。

3. 活動篩選邏輯

• 初始選擇第一個活動（排序后最早結束的活動），activityCount?初始化為 1。
• 遍歷后續活動時，通過?activities[i][0] >= lastActivityEndTime?判斷是否重疊：
  • 若滿足條件：選擇該活動，activityCount?加 1，并更新?lastActivityEndTime?為當前活動的結束時間。
  • 若不滿足：跳過該活動，繼續遍歷下一個。

算法效率分析

時間復雜度	空間復雜度	說明
O(n log n)	O(n)	時間復雜度由排序操作主導（sort?函數的時間復雜度為 O (n log n)）；空間復雜度用于存儲活動列表，為 O (n)（n 為活動數量）。

該效率是活動選擇問題的最優解 —— 貪心算法無需額外的動態規劃數組，在時間和空間上均優于其他解法。

測試用例驗證

測試用例 1：常規輸入（示例輸入）

• 開始時間：1 3 0 5 8 5
• 結束時間：2 4 6 7 9 9
• 排序后活動：[1,2]、[3,4]、[0,6]、[5,7]、[5,9]、[8,9]
• 選中活動：[1,2]、[3,4]、[5,7]、[8,9]
• 輸出：4（正確）

測試用例 2：空輸入

• 開始時間：（直接回車）
• 結束時間：（直接回車）
• 輸出：0（正確）

測試用例 3：所有活動重疊

• 開始時間：1 2 3
• 結束時間：4 5 6
• 選中活動：[1,4]
• 輸出：1（正確）

測試用例 4：活動無重疊

• 開始時間：1 3 5
• 結束時間：2 4 6
• 選中活動：[1,2]、[3,4]、[5,6]
• 輸出：3（正確）

總結

活動選擇問題是貪心算法的典型應用，核心在于 “優先選擇最早結束的活動” 這一局部最優策略。本文的實現通過清晰的數據組織、嚴格的輸入校驗和高效的排序篩選邏輯，確保了代碼的正確性和可讀性。

該解法不僅適用于經典的活動選擇場景，還可擴展到類似問題（如會議安排、任務調度等），只需將 “活動” 替換為對應的場景實體（如會議、任務），邏輯完全復用。