用于处理间隔的数据结构

Question

我得到了一系列不能重叠的时间间隔(t_start，t_end)，即: t_end(i) > t_start(i+1)。我想做以下操作：

1)添加新的(并)区间{(1,4)，(8,10)} U (3,7) = {(1,7)，(8,10)}

2)取间隔[ (1,7) - (3,5) = {(1,3)，(5,7)}

3)检查点或区间是否与我的序列中的区间重叠(交集)

4)在某个点{(1,4)，(7，8)}之后找到第一个最小长度的“非区间”：在4和7之间有一个长度为3的“非区间”。

我想知道实现这一点的好方法，而且复杂度很低(所有操作的log n都可以做到)。

相关问题：Data structure for quick time interval look up

Answer 1

听起来你可以使用一个包含所有边界时间的平衡二叉树。

例如，将{( 1，4)，( 8，10)，( 12，15 )}表示为包含1，4，8，10，12和15的树。

每个节点都需要说明它是间隔的开始还是结束。所以：

                          8 (start)
                         /        \
                1 (start)         12 (start)
                      \             /      \
                     4 (end)   10 (end)   15 (end)

(在这里，所有的"end“节点都巧合地在底部结束。)

然后我认为你可以在O(log )时间内完成所有操作。用于添加间隔的

• 找到开始时间。如果它已经在树中作为开始时间，你可以把它留在那里。如果它已经作为结束时间出现在树中，则需要将其删除。如果它不在树中，并且在现有的时间间隔内没有落下，那么您将需要添加它。否则你不想添加它。
• 找到停止时间，使用相同的方法来确定你是需要添加它，删除它，还是两者都不需要。
• 现在你只想添加或删除上面提到的开始和停止节点，同时删除中间的所有现有节点。要做到这一点，您只需在树中这两个位置或其正上方重新构建树节点。如果树的高度是O(log )，这可以通过使用平衡树来保证，这需要O(log )时间。

(免责声明:如果您在C++中执行显式内存管理，则在执行此操作时可能会释放超过O(log )个内存块，但我认为释放节点所需的时间应该计入添加该节点的人。)

删除间隔在很大程度上是相同的。

检查点或间隔很简单。

在给定时间后查找至少给定大小的第一个间隙也可以在O(log )内完成，如果您还在每个节点上缓存两条以上的信息：

• 在每个开始节点(最左边除外)中，紧邻左侧的间隙的大小。
• 在每个节点中，该子树中出现的最大间隙的大小。

要查找在给定时间之后出现的给定大小的第一个间隙，请首先在树中查找该时间。然后继续往上走，直到到达一个声称包含足够大间隙的节点。如果你从右边上来，你知道这个缺口在左边，所以你忽略了它，继续往上走。否则你就是从左边来的。如果该节点是起始节点，请检查其左侧的间隙是否足够大。如果是这样的话，你就完成了。否则，足够大的差距必须在右边的某个地方。向右走，然后一直往下走，直到你找到缺口。同样，因为树的高度是O(log )，所以遍历它三次(向下、向上和可能再次向下)是O(log )。

Answer 2

在不了解更多细节的情况下，我建议阅读有关Interval Trees的内容。区间树是更一般的kd-trees的一维特殊情况，并且具有O(n log n)构造时间和O(log n)典型运算时间。具体的算法实现你需要自己去找，但是你可以从CGAL开始。

Answer 3

我知道您已经接受了答案，但是既然您表示可能会在C++中实现，那么您还可以看看Boosts Container Library (http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html)。