学生有n项活动申请使用某一个会议室,每项活动都有一个开始时间和一个结束时间。任何两个活动都不能同时使用这个会议室。问如何安排这些活动,使得被安排活动的数量达到最多?c语言实现
时间: 2024-02-11 07:05:51 浏览: 33
以下是基于贪心算法的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义活动结构体
typedef struct {
int start;
int end;
} Activity;
// 对活动按照开始时间排序
int cmp(const void* a, const void* b) {
return ((Activity*)a)->start - ((Activity*)b)->start;
}
// 贪心算法选择活动
int selectActivities(Activity activities[], int n) {
int count = 1;
int lastEnd = activities[0].end;
for (int i = 1; i < n; i++) {
if (activities[i].start >= lastEnd) {
count++;
lastEnd = activities[i].end;
}
}
return count;
}
int main() {
int n;
scanf("%d", &n);
Activity activities[n];
for (int i = 0; i < n; i++) {
scanf("%d %d", &activities[i].start, &activities[i].end);
}
// 按照开始时间对活动进行排序
qsort(activities, n, sizeof(Activity), cmp);
// 贪心算法选择活动
int count = selectActivities(activities, n);
printf("%d\n", count);
return 0;
}
```
输入格式为:
```
n
start1 end1
start2 end2
...
startn endn
```
其中n为活动数量,start1~startn和end1~endn分别为活动的开始时间和结束时间。输出为能够安排的最大活动数量。
注:该实现中没有对输入进行错误处理,实际使用时需要注意。