用C语言写Problem Description 已知N=12个事件的发生时刻和结束时刻(下表,并已按结束时刻升序排序)。一些在时间上没有重叠的事件可以构成一个事件序列,如{2,8,10},事件序列包含的事件数目,称为该事件序列的长度。编程找出一个最长的事件序列。 Input Description 第一行输入一个整数0<N<1000,表示事件的数量。 接下来输入N行,输入两个数begin[i],end[i],分别表示时间的发生时刻与结束时刻,0<=i<N。 Output Description 输出最长的时间序列。 Sample Input 12 1 3 3 4 0 7 3 8 2 9 5 10 6 12 4 14 10 15 8 18 15 19 15 20 Sample Output {0,1,5,8,10}
时间: 2024-02-11 10:09:39 浏览: 26
以下是C语言的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
struct event {
int begin;
int end;
};
int cmp(const void *a, const void *b) {
return ((struct event *)a)->end - ((struct event *)b)->end;
}
int main() {
int n, i, last_end = -1, len = 0;
struct event events[MAX_N];
int result[MAX_N];
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d %d", &events[i].begin, &events[i].end);
}
qsort(events, n, sizeof(struct event), cmp);
for (i = 0; i < n; i++) {
if (events[i].begin >= last_end) {
result[len++] = i;
last_end = events[i].end;
}
}
printf("{");
for (i = 0; i < len; i++) {
printf("%d", result[i]);
if (i < len - 1) {
printf(",");
}
}
printf("}");
return 0;
}
```
首先,我们定义了一个结构体event来存储每个事件的开始时间和结束时间。
然后,我们使用标准库函数qsort对所有事件按照结束时间升序排序。
接着,我们遍历所有事件,对于每个事件,如果其开始时间大于等于last_end,则将其加入到result中,并更新last_end为该事件的结束时间。
最后,我们输出result即为最长的事件序列。
注意,由于题目要求输出的是事件的下标,因此result中存储的是事件的下标,而不是开始时间或结束时间。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)