查找最大并发进程数的时间间隔

Question

系统以格式：startTime，endTime，Request生成日志。 如何计算最大并发请求数的时间间隔？ 我尝试使用hashmap作为键值请求计数的时间戳。如果每个请求和更新计数器的开始和时间之间的所有值都填充密钥，但是如果时间戳精确到毫秒，这将需要巨大的空间。

Answer 1

转换列表以事件与属性TS，值

STARTTIME：123456，结束时间：23456，请求：....变为两个事件：

（123456，1） （23456， -1）

您现在的请求数量将是事件的两倍。

如果您按时间戳排序这些事件，则可以对它们进行迭代并加上和减去这些值。跟踪您所看到的最大值和发生的时间戳。

由于您需要对事件进行排序并使用O（n）空间，因此它将在O（nlogn）中运行。