在流中合并重叠间隔的摊销复杂性
amortized complexity of merging overlapping intervals in a stream
对于合并数据流中区间的问题，一种方法
是将每个传入间隔存储在最小堆中（按间隔的开始排序）。每个 add(interval) 都会将间隔添加到堆中，并在需要时将其与重叠间隔合并。
据说每 add 的复杂度可能比 logn 差，但摊销时间将为 logn。
关于为什么这是真的，我无法真正形成直觉。我知道如果需要合并 add(interval) 可能比 logn 花费更长的时间，因为我们需要从堆中弹出元素，但我如何向自己证明（从直觉上或数学上）平均值将是 logn？
这是一个很好的问题，因为许多分摊算法都有类似的简单成本证明：
add 操作需要 O((m+1) * log N) 时间，其中 m 是需要执行的合并数。
但是，每次合并都会删除 之前添加的元素。由于添加的元素只能删除一次，我们可以将合并和删除该元素的 O(log N) 成本转移到创建它的 add 操作，我们得出每 add.
的摊销成本 O(log N)
对于合并数据流中区间的问题，一种方法
是将每个传入间隔存储在最小堆中（按间隔的开始排序）。每个 add(interval) 都会将间隔添加到堆中，并在需要时将其与重叠间隔合并。
据说每 add 的复杂度可能比 logn 差，但摊销时间将为 logn。
关于为什么这是真的，我无法真正形成直觉。我知道如果需要合并 add(interval) 可能比 logn 花费更长的时间，因为我们需要从堆中弹出元素，但我如何向自己证明（从直觉上或数学上）平均值将是 logn？
这是一个很好的问题，因为许多分摊算法都有类似的简单成本证明：
add 操作需要 O((m+1) * log N) 时间，其中 m 是需要执行的合并数。
但是，每次合并都会删除 之前添加的元素。由于添加的元素只能删除一次，我们可以将合并和删除该元素的 O(log N) 成本转移到创建它的 add 操作，我们得出每 add.