处理间隔的数据结构 [英] Data structure for handling intervals

问题描述

我有一系列时间间隔（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）}：长度为3到4之间的非间隔]。

我想知道实现这一点的好方法，复杂性很低（所有操作都需要登录）。

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

解决方案

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

$ b $例如，代表{（1,4），（8,10），（12,15）}作为一个树包含1，4，8，10，12和15。

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

  8（开始）
 / \ 
 1（开始）12（开始）
 \ / \ 
 4（结束）10（结束）15（结束）
  

（这里所有的结束节点都以巧合结束在底部。）

然后我想你可以把所有的操作都放在O（log n）时间。 添加间隔：

• 查找开始时间。如果它已经在树上作为开始的时间，你可以把它留在那里。如果它已经在树中作为结束时间，您将需要删除它。如果它不在树状结构和中，它不会在现有间隔期间落下，您将需要添加它。否则你不想添加它。




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




• 现在您只想添加或删除上述启动和停止节点，并同时删除其间的所有现有节点。要做到这一点，您只需要在树上的两个位置重建树结点，或者直接在之上。如果树的高度是O（log n），那么可以通过使用平衡树来保证，这需要O（log n）时间。

（免责声明：如果您使用C ++并进行显式内存管理，则可能会在执行此操作时最多释放超过O（日志n）的内存，但实际上是这样的时间

删除间隔大致相同。

检查点或间隔是简单的。

查找第一个差距如果您还在每个节点缓存两条信息，则可以在O（日志n）中完成给定时间后给定的大小 ：

• 在每个起始节点（除最左边的节点之外），间隙的大小立即向左。




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

要查找在给定时间后出现的给定尺寸的第一个间隙，首先在树中找到时间。然后走上去，直到你到达一个声称包含足够大的差距的节点。如果你从右边走过来，你知道这个差距在左边，所以你忽略它，继续走。否则你来自左边。如果节点是起始节点，请检查其左侧的间隙是否足够大。如果是这样，你就完成了。否则，足够大的差距必须在右边。向右走，继续向下，直到找到差距。再次，因为树的高度是O（log n），步行三次（向下，向上，也可能再次下降）为O（log n）。

I have got a series of time intervals (t_start,t_end), that cannot overlap, i.e.: t_end(i) > t_start(i+1). I want to do the following operations:

1) Add new (Union of) intervals [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) Take intervals out [ (1,7) - (3,5) = {(1,3),(5,7)}
3) Checking whether a point or a interval overlaps with an interval in my series (intersection)
4) Finding the first "non-interval" of a minimum length after some point [ {(1,4),(7,8)}: there is a "non-interval" of length 3 between 4 and 7 ].

I want to know good ways of implementing this, with low complexities (log n for all operations would do it).

Related question: Data structure for quick time interval look up

解决方案

It sounds like you could just use a balanced binary tree of all the boundary times.

For example, represent {(1,4), (8,10), (12,15)} as a tree containing 1, 4, 8, 10, 12, and 15.

Each node needs to say whether it's the start or end of an interval. So:

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

(Here all the "end" nodes ended up at the bottom by coincidence.)

Then I think you can have all your operations in O(log n) time. To add an interval:

• Find the start time. If it's already in the tree as a start time, you can leave it there. If it's already in the tree as an end time, you'll want to remove it. If it's not in the tree and it doesn't fall during an existing interval, you'll want to add it. Otherwise you don't want to add it.

• Find the stop time, using the same method to find out if you need to add it, remove it, or neither.

• Now you just want to add or remove the abovementioned start and stop nodes and, at the same time, delete all the existing nodes in between. To do this you only need to rebuild the tree nodes at or directly above those two places in the tree. If the height of the tree is O(log n), which you can guarantee by using a balanced tree, this takes O(log n) time.

(Disclaimer: If you're in C++ and doing explicit memory management, you might end up freeing more than O(log n) pieces of memory as you do this, but really the time it takes to free a node should be billed to whoever added it, I think.)

Removing an interval is largely the same.

Checking a point or interval is straightforward.

Finding the first gap of at least a given size after a given time can be done in O(log n) too, if you also cache two more pieces of information per node:

• In each start node (other than the leftmost), the size of the gap immediately to the left.

• In every node, the size of the largest gap that appears in that subtree.

To find the first gap of a given size that appears after a given time, first find that time in the tree. Then walk up until you reach a node that claims to contain a large enough gap. If you came up from the right, you know this gap is to the left, so you ignore it and keep walking up. Otherwise you came from the left. If the node is a start node, check to see if the gap to its left is large enough. If so, you're done. Otherwise, the large-enough gap must be somewhere to the right. Walk down to the right and continue down until you find the gap. Again, because the height of the tree is O(log n), walking it three times (down, up, and possibly down again) is O(log n).

这篇关于处理间隔的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！