我正在寻找一种算法来完成以下任务。我有一个跨越时间段的事件的时间表,这些时间段可以重叠。我想将这些事件折叠成一个时间线非重叠的时间段,每个时间段由一个或多个事件的存在定义。
虽然概念上很简单,但要捕获所有可能的情况并适当地划分时间线可能会有点混乱。
为了说明(这里的水平轴是时间):
Event A -----
Event B ----
变成了
Event A ---
Event A+B --
Event B --
另一个例子:
A -----------
B ---
C --
变成:
A ---
A+B
我有一个包含最大元素的整数列表,我需要跟踪列表中的最大元素:
[3, 1, 2] (3 is the max)
每一段时间,我都会得到一个新的随机元素,将其添加到列表的末尾,然后在固定时间内删除列表中的第一个元素。因此,在当前时间段结束时,我的列表将像这样转换:
[3, 1, 2] (3 is the max)
-> [3, 1, 2, -5] (don't care about max at this moment)
-> [1, 2, -5] (now 2 is the max)
我可以根据列表中的值保持一个优先级队列,给出O(log(n