algorithm - 处理间隔的数据结构

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)

(此处所有“结束”节点巧合地位于底部。)

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

• 找到开始时间。如果它已经作为开始时间在树中，则可以将其留在那里。如果它已经在树中作为结束时间，您将要删除它。如果它不在树中并且它没有在现有间隔内掉落，您将要添加它。否则你不想添加它。

• 找到停止时间，使用相同的方法找出是否需要添加它、删除它或两者都不需要。

• 现在您只想添加或删除上述开始和停止节点，同时删除其间的所有现有节点。为此，您只需要在树中的这两个位置或正上方重建树节点。如果树的高度是 O(log n)，你可以通过使用平衡树来保证，这需要 O(log n) 时间。

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

删除间隔大致相同。

检查点或区间很简单。

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

• 在每个起始节点(最左边的除外)中，紧靠左侧的间隙大小。

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

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