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