处理间隔的数据结构

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都可以).

相关问题:查询快速时间间隔的数据结构

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)

(这里所有的"结束"节点都巧合地落在了底部.)

然后我认为你可以在O(log n)时间内完成所有操作.要添加间隔:

• 找到开始时间.如果它已经在树中作为开始时间,您可以将它留在那里.如果它已经在树中作为结束时间,您将要删除它.如果它不在树中并且在现有间隔期间不会下降,则您需要添加它.否则你不想添加它.

• 找到停止时间,使用相同的方法找出是否需要添加,删除或两者都没有.

• 现在您只想添加或删除上述启动和停止节点,同时删除其间的所有现有节点.要执行此操作,您只需要在树中的这两个位置或其正上方重建树节点.如果树的高度为O(log n),您可以使用平衡树来保证,这需要O(log n)时间.

(免责声明:如果您使用C++并进行显式内存管理,那么在执行此操作时最终可能会释放超过O(log n)内存的内存,但实际上,释放节点所需的时间应该向任何人收取费用添加它,我想.)

删除间隔大致相同.

检查点或间隔很简单.

如果您还为每个节点缓存两条以上的信息,那么在给定时间之后找到至少给定大小的第一个间隙也可以在O(log n)中完成:

• 在每个起始节点(除了最左边)之外,紧靠左边的间隙的大小.

• 在每个节点中,该子树中出现的最大间隙的大小.

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

Answer 2

不知道具体细节,我建议阅读有关间隔树的内容.区间树是更通用的kd树的特殊1维情况,并且具有O(n log n)构造时间和O(log n)典型的操作时间.您需要自己找到精确的算法实现,但您可以从查看CGAL开始.