java - 查找具有最大并发进程数的时间间隔

Question

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

Answer 1

将列表转换为具有属性 ts、value 的事件

startTime: 123456, endTime:23456, Request: ....变成两个事件:

(123456, 1)(23456, -1)

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

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

这在 O(nlogn) 中运行，因为您需要对事件进行排序并占用 O(n) 空间。