用c语言完成,设有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相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。 利用贪心算法的性质,通过选择适当的贪心策略的贪心算法解决活动安排问题,且能求得活动安排的最优解。
时间: 2024-03-27 20:38:45 浏览: 74
以下是用C语言实现的活动安排问题的贪心算法:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int start_time; // 活动开始时间
int end_time; // 活动结束时间
} Activity;
int cmp(const void* a, const void* b) {
Activity* act1 = (Activity*) a;
Activity* act2 = (Activity*) b;
return act1->end_time - act2->end_time;
}
int main() {
int n; // 活动数
printf("请输入活动数:");
scanf("%d", &n);
Activity* activities = (Activity*) malloc(n * sizeof(Activity));
printf("请依次输入每个活动的开始时间和结束时间:\n");
for (int i = 0; i < n; i++) {
scanf("%d%d", &activities[i].start_time, &activities[i].end_time);
}
qsort(activities, n, sizeof(Activity), cmp); // 按结束时间排序
// 贪心选择
int count = 1; // 最大相容活动数
int end_time = activities[0].end_time;
for (int i = 1; i < n; i++) {
if (activities[i].start_time >= end_time) { // 选取相容活动
count++;
end_time = activities[i].end_time;
}
}
printf("最大相容活动数为:%d\n", count);
free(activities);
return 0;
}
```
该算法先将活动按结束时间从小到大排序,然后从第一个活动开始,依次选择结束时间最早且与前面已选活动相容的活动,直到无法再选择为止。最后输出所选活动的数量即为最大相容活动数。
需要注意的是,该算法的时间复杂度为O(nlogn),其中n为活动数,主要来自于排序操作。
阅读全文