內容
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
3 0 6 5 7 8 9 5 9 1 2 3 4 0 5 0 0 6 10 5 6 0 3 0 5 3 5 4 5 0 0 1 5 3 9 0 0
範例輸出 #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)
文章標籤
全站熱搜
