题目不少于5个字,所以整了个括号凑字数
首先我想到的是用一个数组来记录每一秒的在线人数
但是即使是short类型(2字节),也会用到60 * 60 * 24 * 30 * 12 * 60 * 2 / 1024 / 1024 = 3,559.5703125 MB
而题目上限是256MB,超了,虽然时间复杂度是O(n)
第二个想到的是一个一个处理数据,用一个数组记录目前的时间区间,如果新数据没有和目前的时间区间重合,就新创建一个,如果重合,该时间区间就缩小到重合部分,而该时间区间的重合数加一
这个方法的时间复杂度最低是O(n)最高是O(n * (n + 1) / 2)
但是这个方法不可行,因为记录的时间区间是不断缩小的,如果有新的时间区间和旧的记录的较大的时间区间重合的话,之前的重合数就没有记录下来
如[1,5), [4,5), [1,2), [1,2),答案是3,而按这个方法计算是2
所以每一个时间区间都要比较
设置一个临时的时间区间,一一等于每一个时间区间,然后在每一轮对所有的时间区间进行比较
而且不断缩小到重合部分,记录重合数,对所有的重合数取最大值,就是答案了
时间复杂度是O(n ^ 2)
代码如下:
#include<stdio.h>
struct Time{
int A;
int B;
}time[1000];
int jud(int A1, int B1, int A2, int B2);
int main(void)
{
int n, maxn = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d%d", &time[i].A, &time[i].B);
for(int i = 0; i < n; i++)
{
struct Time tmp;
int count = 0;
tmp.A = time[i].A, tmp.B = time[i].B;
for(int j = 0; j < n; j++)
if(jud(time[j].A, time[j].B, tmp.A, tmp.B))
{
tmp.A = (tmp.A > time[j].A) ? tmp.A : time[j].A;
tmp.B = (tmp.B < time[j].B) ? tmp.B : time[j].B;
count++;
}
maxn = (maxn > count) ? maxn : count;
}
printf("%d", maxn);
return 0;
}
int jud(int A1, int B1, int A2, int B2)
{
if(B1 <= A2 || A1 >= B2)
return 0;
return 1;
}