活动安排问题贪心算法c语言代码
时间: 2024-05-15 11:10:46 浏览: 148
活动安排问题是一种经典的贪心算法问题。该问题可以简述为:有一组活动,每个活动在同一时间只能有一个人参加,求出最大化参加活动的人数。
下面是一个使用C语言实现的活动安排问题贪心算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义结构体表示活动
struct Activity {
int start; // 活动开始时间
int end; // 活动结束时间
};
// 比较函数,按照结束时间从小到大排序
int cmp(const void *a, const void *b) {
struct Activity *activity1 = (struct Activity *)a;
struct Activity *activity2 = (struct Activity *)b;
return activity1->end - activity2->end;
}
// 贪心算法求解活动安排问题
int activitySelection(struct Activity activities[], int n) {
// 按照结束时间从小到大排序
qsort(activities, n, sizeof(struct Activity), cmp);
int count = 1; // 最少有一个活动可以参加
int i = 0;
for (int j = 1; j < n; j++) {
// 如果当前活动的开始时间晚于等于上一个活动的结束时间
if (activities[j].start >= activities[i].end) {
count++;
i = j;
}
}
return count;
}
int main() {
struct Activity activities[] = {
{1, 3},
{2, 5},
{3, 7},
{4, 8},
{5, 9},
{6, 10},
{8, 11}
};
int n = sizeof(activities) / sizeof(activities);
int count = activitySelection(activities, n);
printf("最大化参加活动的人数为:%d\n", count);
return 0;
}
```
阅读全文