C语言贪心算法活动安排问题
时间: 2023-12-02 11:43:00 浏览: 128
贪心算法活动安排问题
5星 · 资源好评率100%
以下是C语言贪心算法活动安排问题的实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 活动结构体
struct Activity {
int start; // 开始时间
int end; // 结束时间
};
// 比较函数,按照结束时间升序排序
int cmp(const void *a, const void *b) {
return ((struct Activity *)a)->end - ((struct Activity *)b)->end;
}
// 贪心算法求解活动安排问题
void activitySelection(struct Activity activities[], int n) {
// 按照结束时间升序排序
qsort(activities, n, sizeof(struct Activity), cmp);
// 第一个活动一定被选中
int i = 0;
printf("Selected activity: %d ", i);
// 遍历剩余活动
for (int j = 1; j < n; j++) {
// 如果当前活动的开始时间晚于等于上一个活动的结束时间,则选中该活动
if (activities[j].start >= activities[i].end) {
printf("%d ", j);
i = j;
}
}
}
int main() {
// 测试数据
struct Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}};
int n = sizeof(activities) / sizeof(activities[0]);
// 求解活动安排问题
activitySelection(activities, n);
return 0;
}
```
阅读全文