输入格式: 第一行是一个整数n (1<n<10000)表示共有n个活动申请。 随后的n行,每行有两个正整数Bi, Ei (0<Bi<Ei<10000),分别表示第i个活动的起始与结束时间,即表示第i个活动申请占用礼堂的时间段为[Bi,Ei]。 输出格式: 输出最多能够安排的活动数目。C语言实现
时间: 2024-03-07 07:50:17 浏览: 86
这是一个经典的区间调度问题,可以使用贪心算法解决。具体思路如下:
1. 将所有活动按照结束时间从早到晚排序。
2. 选择第一个活动,并将其结束时间作为当前时间。
3. 依次考虑每个活动,如果其开始时间在当前时间之后,则选择该活动,并将其结束时间作为当前时间。
4. 最终选择的活动即为最多能够安排的活动数目。
下面是完整的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 10000
struct activity {
int start;
int end;
};
int cmp(const void *a, const void *b)
{
struct activity *x = (struct activity *)a;
struct activity *y = (struct activity *)b;
return x->end - y->end;
}
int main()
{
int n;
struct activity act[MAX_N];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &act[i].start, &act[i].end);
}
qsort(act, n, sizeof(struct activity), cmp);
int cnt = 1;
int cur = act[0].end;
for (int i = 1; i < n; i++) {
if (act[i].start >= cur) {
cnt++;
cur = act[i].end;
}
}
printf("%d\n", cnt);
return 0;
}
```
注意:在使用 qsort 函数进行排序时,要自定义比较函数 cmp,按照结束时间从早到晚排序。在选择活动时,要判断其开始时间是否在当前时间之后,如果是则选择该活动,并将其结束时间作为当前时间。
阅读全文