首页 > 代码库 > hdu 2037简单贪心--活动安排问题

hdu 2037简单贪心--活动安排问题

2024-07-12 16:37:55   218人阅读

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源

      设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有 一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。 

      首先我们要做的就是，根据结束时间，对储存开始时间和结束时间的两个数组进行升序排序，然后每次贪心选择最前面的当然要保证相容。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2037


代码：

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4  5 struct ss{ 6 int start; 7 int end; 8 }; 9 10 int cmp(ss x,ss y){11 return x.end < y.end;12 }13 int main(){14 ss time[110];15 int a[110];16 int n,ans;17 while(scanf("%d",&n) && n){18         ans = 1;19   for(int i = 0; i < n; i++){20     scanf("%d%d",&time[i].start,&time[i].end);21   }22    sort(time,time+n,cmp);23    a[0] = time[0].end;24    int j = 0;25    for(int i = 1;i < n; i ++){26     if(time[i].start >= a[j]){27       ans ++;28       a[++j] = time[i].end;29     }30    }31 printf("%d\n",ans);32 }33 return 0;34 }
View Code


联系
我们