e563 - 12694 - Meeting Room Arrangement

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在給定的活動列表中，能夠安排在會議室中且互不重疊的最大活動數量。會議室的可用時間為 0 到 10 小時。每個活動都有一個開始時間和結束時間。

解題思路

本題可以使用貪心演算法解決。核心思想是按照活動的結束時間進行排序，然後從最早結束的活動開始選擇。如果當前活動的開始時間大於或等於上一個已選擇活動的結束時間，則選擇該活動。這樣可以最大化在有限時間內安排的活動數量。

具體步驟如下：

1. 讀取每天的活動列表，直到遇到 s = 0 且 e = 0 的終止標記。
2. 使用自定義比較函數 cmp 按照活動的結束時間升序排序活動列表。如果結束時間相同，則按照開始時間降序排序。
3. 初始化已安排的活動數量 ans 為 0，以及會議室的可用時間 time 為 0。
4. 遍歷排序後的活動列表。對於每個活動，如果其開始時間大於或等於 time，則選擇該活動，將 ans 加 1，並將 time 更新為該活動的結束時間。
5. 輸出每天可以安排的最大活動數量 ans。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是每天活動的數量。排序操作佔據主導地位。
• 空間複雜度: O(n)，用於儲存活動列表。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
struct day{
	int s,e;
};
bool cmp(day x,day y){
	if(y.e<x.e||(y.e==x.e&&y.s>x.s))return 0;
	return 1;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		day a[20];
		int it=0,ans=0,time=0;
		while(cin >> a[it].s >> a[it].e){
			if(a[it].s==0&&a[it].e==0)break;
			++it;
		}
		sort(a,a+it,cmp);
		for(int i=0;i<it;++i){
			if(a[i].s>=time){
				time=a[i].e;
				++ans;
			} 
		}
		cout << ans << "\n";
	}
}