高中生城市解題:e563: 12694 - Meeting Room Arrangement－資工趴趴熊的小天地

內容

PSU工程學院設有一個寬敞的會議室，可供教職員工辦活動和開會。會議室的使用必須提前預約。
由於會議室每天有10個小時可用，並且可能有多個活動要使用會議室，因此最佳使用策略是使一天中的活動數量最大化。
假設會議室的可用時間為0到10 (總共10小時)。
給定每個候選活動的開始時間和結束時間，請你寫一個程式來選擇適合會議室的活動(即活動的時間不重疊)，並給出一天可以辦的最大活動數量。

輸入說明

第一行有一個正整數n (1 ≤ n ≤ 100)，n代表需要確認的天數。
每天都包含候選活動的時間(每天少於20個活動)。
每個活動時間包括2個整數s (0 ≤ s ≤ 9)和f (1 ≤ f ≤ 10)。
s代表此活動開始時間，f代表此活動結束時間
並且活動的s < f。
如果s = f = 0代表該天候選活動的結尾(這行不是活動不用處理)。

輸出說明

對於每天，請輸出當天可在會議室安排的最大活動數量。

範例輸入 #1

範例輸出 #1

4
4
1

C++

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std;
struct node{
	int s;
	int f;
};
bool cmp(node a,node b){
	return a.f<b.f;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	while(n--){
		int s,f;
		int cnt=0; //計算幾筆測資 
		node schedul[20];
		while(cin>>s>>f){
			if(s==0 && f==0)break;
			schedul[cnt].s=s;
			schedul[cnt].f=f;
			cnt++;
		}
		sort(schedul,schedul+cnt,cmp);
		for(int i=0;i<cnt;i++){
			cout<<"node "<<schedul[i].s<<" "<<schedul[i].f<<"\n";
		}
		int ans=1;
		int temp=schedul[0].f;
		for(int i=1;i<cnt;i++){
			if(schedul[i].s>=temp){
				ans++;temp=schedul[i].f;
			}
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}

python:

t=int(input())
for _ in range(t):
    arr=[]
    cnt=0
    while True:
        s,f=map(int,input().split())
        if s==0 and f==0:break
        arr.append([s,f])
        cnt+=1
    
    arr.sort(key=lambda x:(x[1],x[0]))
    
    #print(arr)
    temp=arr[0][1]
    ans=1
    for i in range(1,len(arr)):
        if arr[i][0]>=temp:
            ans+=1
            temp=arr[i][1]
    print(ans)