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

例如，将{（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（logn），因此将其行走3次（向下，向上，甚至可能再次向下）为O（log n）。