題型描述
有 n 個活動需要使用同一資源，且同一時段內只有一個活動能使用該資源，每個活動 i 都有起始時間 si 和結束時間 ei （si < ei），如果安排活動 i，則它在時間區間 [si，ei) 內占用資源，若區間 [si， ei) 與區間 [sj，ej) 不相交，則稱活動 i 與活動 j 相容，
活動安排問題即，安排活動使盡可能多的活動相容，本質為，在所給的活動集合中選出最大的相容活動子集合，
解題思路
每次都選擇結束時間最早的活動，為未安排活動留下盡可能多的時間，該貪心演算法的本質是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動，
（貪心演算法 是指在對問題求解時，不從整體最優上加以考慮，總是做出某種意義上的區域最優解，）
解題步驟
1.將活動按結束時間單調遞增排序；
2.依次選擇結束時間最早的活動，并計數，
實體題解
兼容問題
題目描述
設有 n 個任務，其中每個任務有一個起始時間 si 和一個結束時間 ei ，且 si < ei ，同一時間只能完成一個任務，如果選擇了任務 i ，則它在時間區間 [si ，ei) 內占用資源，若區間 [si，ei) 與區間 [sj， ej)不相交，則稱任務 i 與任務 j是相容的，
那么，對于給定的任務時間區間，能互相兼容的最大任務個數是多少呢？輸入格式
第一行一個整數 n （1<=n<=1000）；
接下來 n 行，每行兩個整數 si 和 ei ，輸出格式
互相兼容的最大任務個數，
完整代碼
#include<stdio.h>
int main(){
int n,i,j,number=1,t,final;
int s[1200],e[1200];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d",&s[i],&e[i]);
}
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(e[j]>e[j+1]){
t=s[j];
s[j]=s[j+1];
s[j+1]=t;
t=e[j];
e[j]=e[j+1];
e[j+1]=t;
}
}
}
final=e[0];
for(i=1;i<n;i++){
if(s[i]>=final){
number++;
final=e[i];
}
}
printf("%d",number);
return 0;
}
參考資料：
1.從零開始學貪心演算法
2.演算法模板
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/47151.html
標籤：C
下一篇：德州撲克題解