PRoblem Description
學(xué)校的大學(xué)生藝術(shù)中心周日將面向全校各個學(xué)院的學(xué)生社團開放,但活動中心同時只能供一個社團活動使用,并且每一個社團活動開始后都不能中斷。現(xiàn)在各個社團都提交了他們使用該中心的活動計劃(即活動的開始時刻和截止時刻)。請設(shè)計一個算法來找到一個最佳的分配序列,以能夠在大學(xué)生藝術(shù)中心安排不沖突的盡可能多的社團活動。比如有5個活動,開始與截止時刻分別為:
最佳安排序列為:1,4,5。 Input
第一行輸入活動數(shù)目n(0<n<100);以后輸入n行,分別輸入序號為1到n的活動使用中心的開始時刻a與截止時刻b(a,b為整數(shù)且0<=a,b<24,a,b輸入以空格分隔)。 Output
輸出最佳安排序列所包含的各個活動(按照活動被安排的次序,兩個活動之間用逗號分隔)。 Example Input
68 109 1611 1614 1510 147 11Example Output
1,5,4#include<stdio.h>struct node{ int begin; int end; int ans;}show[111],t;int main(){ int n,i,j,ach[111]; while(~scanf("%d",&n)) { for(i=0;i<n;i++) { scanf("%d%d",&show[i].begin,&show[i].end); show[i].ans=i+1; } for(i=0;i<n;i++) { for(j=0;j<n-i-1;j++) { if(show[j].end>show[j+1].end) {t=show[j];show[j]=show[j+1];show[j+1]=t;} } } int num=0,k=0; for(i=0;i<n;i++) { if(show[i].begin>=k) { k=show[i].end; ach[num]=show[i].ans; num++; } } for(i=0;i<num;i++) { if(i==num-1) printf("%d/n",ach[i]); else printf("%d,",ach[i]); } } return 0;}