- #include <bits/stdc++.h>
- //#include <iostream>
- //#include <vector>
- //#include <algorithm>
- using namespace std;
- // 定義活動結構
- struct Activity {
- int start, end;
- };
- // 排序規則：按照活動的結束時間升序排列
- bool compare(Activity a, Activity b) {
- return a.end < b.end;
- }
- int main() {
- int N;
- cin >> N; // 讀取活動數量
- vector<Activity> activities(N);
- // 讀取每個活動的開始與結束時間
- for (int i = 0; i < N; i++) {
- char comma; // 讀取逗號
- cin >> activities[i].start >> comma >> activities[i].end;
- }
- // 依照活動的結束時間排序
- sort(activities.begin(), activities.end(), compare);
- // 貪心選擇最多活動
- int count = 0, last_end_time = -1;
- for (const auto& act : activities) {
- if (act.start >= last_end_time) {
- count++;
- last_end_time = act.end;
- }
- }
- // 輸出最多能參加的活動數量
- cout << count << endl;
- return 0;
- }
解釋程式
結構體 Activity：
存放活動的 start（開始時間）和 end（結束時間）。
排序函式 compare：
依照活動的結束時間升序排列，確保優先選擇最早結束的活動。
讀取輸入並排序：
使用 vector<Activity> 儲存活動資訊，並用 sort() 排序。
貪心選擇活動：
last_end_time 記錄上一次選擇的活動結束時間。
若目前活動的開始時間 start 不小於 last_end_time，則可以參加。
時間複雜度
排序 O(N log N)
遍歷 O(N)
總時間複雜度：O(N log N)
----------------------------------------
測資
測資 00（基本案例）
輸入：
6
5,9
1,2
3,4
0,6
5,7
8,9
預期輸出：
4
測資 01（時間區間重疊較多）
輸入：
5
1,5
8,10
3,6
2,5
6,9
預期輸出：
2
測資02（所有活動互不衝突，可全選）
輸入：
5
0,1
1,2
2,3
3,4
4,5
預期輸出：
5
測資 03（所有活動結束時間相同，最多只能選一個）
輸入：
4
1,5
2,5
3,5
4,5
預期輸出：
1
測資 04（活動開始時間相同，選擇最早結束的）
輸入：
6
1,10
1,3
1,5
2,6
3,8
4,9
預期輸出：
2
這些測資涵蓋了：
一般情況
高度重疊的活動
完全不衝突的活動
只能選一個活動的極端情況
開始時間相同但結束時間不同的活動 |
