用C语言编写已知N=12个事件的发生时刻和结束时刻(下表,并已按结束时刻升序排序)。一些在时间上没有重叠的事件可以构成一个事件序列,如{2,8,10},事件序列包含的事件数目,称为该事件序列的长度。编程找出一个最长的事件序列。第一行输入一个整数0<N<1000,表示事件的数量。 接下来输入N行,输入两个数begin[i],end[i],分别表示时间的发生时刻与结束时刻,0<=i<N。输出最长的时间序列。
时间: 2024-03-22 12:38:24 浏览: 20
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int begin;
int end;
} Event;
int cmp(const void *a, const void *b) {
Event *e1 = (Event *) a;
Event *e2 = (Event *) b;
return e1->end - e2->end;
}
int main() {
int n;
scanf("%d", &n);
Event *events = (Event *) malloc(sizeof(Event) * n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &events[i].begin, &events[i].end);
}
qsort(events, n, sizeof(Event), cmp);
int *dp = (int *) malloc(sizeof(int) * n);
memset(dp, 0, sizeof(int) * n);
dp[0] = 1;
int max_len = 1;
for (int i = 1; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (events[i].begin >= events[j].end) {
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
max_len = max_len > dp[i] ? max_len : dp[i];
}
printf("%d\n", max_len);
free(events);
free(dp);
return 0;
}
```
算法思路:
1. 将事件按结束时刻升序排序;
2. 定义一个长度为n的数组dp,dp[i]表示以第i个事件为结尾的最长事件序列的长度;
3. 初始化dp[0]=1,即第一个事件的最长序列长度为1;
4. 遍历每个事件,对于第i个事件,遍历之前的所有事件,如果第j个事件的结束时间早于第i个事件的开始时间,则dp[i]=max(dp[i],dp[j]+1);
5. 遍历完所有事件后,dp数组中的最大值即为最长事件序列的长度。
时间复杂度:O(n^2)
可以通过使用堆优化时间复杂度到O(nlogn)。
相关推荐
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)