使用C语言,给出代码解决会场安排问题:学校礼堂每天都会收到许多活动的举办申请,有时活动的计划时间会冲突,因此,需要选择举办一些活动。小刘的工作就是安排学校礼堂的活动,每个时间最多安排一个活动。现在小刘有一些活动计划的时间表,他想尽可能安排更多的活动,请设计算法帮助小刘安排活动。 输入格式: 第一行是一个整数n (1<n<10000)表示共有n个活动申请。 随后的n行,每行有两个正整数Bi, Ei (0<Bi<Ei<10000),分别表示第i个活动的起始与结束时间,即表示第i个活动申请占用礼堂的时间段为[Bi,Ei]。 输出格式: 输出最多能够安排的活动数目。
时间: 2024-03-05 12:49:23 浏览: 136
以下是使用贪心算法的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Activity {
int start;
int end;
} Activity;
int cmp(const void *a, const void *b) {
Activity *p1 = (Activity *)a;
Activity *p2 = (Activity *)b;
return p1->end - p2->end;
}
int main() {
int n;
scanf("%d", &n);
Activity *activities = (Activity *)malloc(sizeof(Activity) * 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 = 1, curEnd = activities[0].end;
for (int i = 1; i < n; i++) {
if (activities[i].start >= curEnd) {
count++;
curEnd = activities[i].end;
}
}
printf("%d\n", count);
free(activities);
return 0;
}
```
算法思路:
1. 将所有活动按照结束时间从小到大排序。
2. 选择第一个活动,将其结束时间作为当前时间。
3. 从第二个活动开始依次判断,如果其开始时间晚于等于当前时间,则选择该活动,将其结束时间作为当前时间。
4. 继续判断下一个活动,直到所有活动都被判断完毕。
5. 输出选择的活动数目。
这个算法的正确性证明:
我们假设活动按照结束时间从小到大排序后的序列为 $A_1, A_2, ..., A_n$,其中 $A_i$ 的结束时间小于等于 $A_{i+1}$ 的结束时间。
我们用 $S$ 来表示当前已经选择的活动集合,$T$ 来表示当前可供选择的活动集合。我们用 $t_i$ 来表示 $A_i$ 是否在 $T$ 中,用 $s_i$ 来表示 $A_i$ 是否在 $S$ 中。
我们用归纳法来证明,对于 $A_1, A_2, ..., A_i$ 这个子序列,贪心算法能够得到最优解。
当 $i=1$ 时,只有一个活动可供选择,显然贪心算法得到的解是最优的。
假设当 $i=k$ 时,贪心算法能够得到最优解,即 $S_k$ 是最优解。现在考虑 $i=k+1$ 时的情况。
如果 $t_{k+1}=0$,即 $A_{k+1}$ 不在 $T$ 中,那么最优解中一定不包含 $A_{k+1}$,因为如果包含 $A_{k+1}$ 那么一定可以将它替换为 $A_i$ 中的某个活动,这个替换不会使得其他活动被排除,但是可以多安排一个活动,这与最优解的定义矛盾。因此,贪心算法可以不考虑 $A_{k+1}$。
如果 $t_{k+1}=1$,即 $A_{k+1}$ 在 $T$ 中,那么最优解一定包含 $A_{k+1}$。为什么呢?因为如果最优解中不包含 $A_{k+1}$,那么我们可以将 $A_{k+1}$ 替换为 $A_i$ 中的某个活动,这个替换不会使得其他活动被排除,但是可以多安排一个活动,这与最优解的定义矛盾。因此,贪心算法选择 $A_{k+1}$。
综上所述,贪心算法可以得到最优解。
阅读全文
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://img-home.csdnimg.cn/images/20241231044901.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![-](https://img-home.csdnimg.cn/images/20241231044901.png)