已知N=12个事件的发生时刻和结束时刻(下表,并已按结束时刻升序排序)。一些在时间上没有重叠的事件可以构成一个事件序列,如{2,8,10},事件序列包含的事件数目,称为该事件序列的长度。编程找出一个最长的事件序列。第一行输入一个整数0<N<1000,表示事件的数量。 接下来输入N行,输入两个数begin[i],end[i],分别表示时间的发生时刻与结束时刻,0<=i<N。用c语言编译
时间: 2024-02-12 18:03:31 浏览: 19
以下是一个用C语言编写的解决方案:
```c
#include <stdio.h>
int main() {
int n, i, j;
scanf("%d", &n);
int begin[n], end[n], dp[n]; // dp数组表示以第i个事件结尾的最长事件序列长度
for (i = 0; i < n; i++) {
scanf("%d%d", &begin[i], &end[i]);
dp[i] = 1; // 初始化为1,即自身就是一个事件序列
}
for (i = 1; i < n; i++) {
for (j = 0; j < i; j++) {
if (end[j] <= begin[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}
int max = 0;
for (i = 0; i < n; i++) {
if (dp[i] > max) {
max = dp[i];
}
}
printf("%d\n", max);
return 0;
}
```
该算法的时间复杂度为$O(n^2)$,通过动态规划实现。具体来说,我们用一个dp数组表示以第i个事件结尾的最长事件序列长度,初始化为1,即自身就是一个事件序列。然后从第二个事件开始,枚举前面的所有事件,如果前面的事件结束时间早于等于当前事件的开始时间,并且前面事件结尾的最长事件序列长度加上1比当前事件结尾的最长事件序列长度要大,那么就更新当前事件的最长事件序列长度。最后找出dp数组中的最大值即可。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)