種子論壇 | 高雄市資訊培育協會學員討論區

標題: 資料結構 501 活動選擇(易) [打印本頁]

作者: may 時間: 5 天前 20:59 標題: 資料結構 501 活動選擇(易)

1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 為了增加曝光度，我們想在有限的時間裡，參加最多活動，請撰寫程式讓使用者輸入活動總數量，以及每個活動的開始與結束時間，計算並輸出最多可以參加多少活動。

(2) 活動參加限制如下：

在相同時間下，僅能選擇一個活動參加。
參加活動的「結束時間」可與下一場活動的「開始時間」相同。
每個活動的「結束時間」必須大於或等於「開始時間」。
提示：活動的開始與結束時間皆為 24 小時制的整點時間。

3. 輸入輸出：
輸入說明
第 1 列：正整數 N（N < 20），表示活動總數量。
第 2~N+1 列：N 個活動的開始、結束時間，並以半形逗號（,）間隔。

輸出說明
最多參加的活動數量。

範例輸入1
6
5,9
1,2
3,4
0,6
5,7
8,9
範例輸出1
4
範例輸入2
5
1,5
8,10
3,6
2,5
6,9
範例輸出2
2

作者: may 時間: 5 天前 21:01

#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
這些測資涵蓋了：

一般情況

高度重疊的活動

完全不衝突的活動

只能選一個活動的極端情況

開始時間相同但結束時間不同的活動

歡迎光臨種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)