按间隔合并范围

Question

给定一组间隔:{1-4,6-7,10-12}添加一个新的间隔:(9,11),以便最终解决方案'合并':输出:{1-4,6-7, 9-12}.合并可能发生在双方(低和高范围).

我看到这个问题在多个地方得到了解答,有人甚至建议使用Interval Tress,但没有解释他们究竟会如何使用它.我所知道的唯一解决方案是按照开始时间的升序排列间隔并迭代它们并尝试合适地合并它们.

如果有人可以帮助我理解我们如何在这个用例中使用区间树,那就太棒了!

[我一直在关注CLRS书中的间隔树,但是他们没有谈论合并,他们所谈论的只是插入和搜索.]

Answer 1

(我假设这意味着间隔永远不会重叠,否则它们会被合并.)

实现此目的的一种方法是存储平衡二进制搜索树,其中每个端点的一个节点具有一个节点.然后将每个节点标记为标记间隔开始的"打开"节点或标记间隔结束的"关闭"节点.

插入新范围时,将针对范围的起点发生以下两种情况之一:

1. 它已经在一个范围内,这意味着您将扩展已存在的范围作为插入的一部分.
2. 它不在一个范围内,所以你将创建一个新的"开放"节点.

要确定您所处的情况,您可以在树中执行前驱搜索范围的起点.如果获得NULL或关闭节点,则需要插入表示范围起点的新打开节点.如果您获得一个开放节点,您将继续延长该间隔.

从那里,您需要确定范围延伸的范围.为此,请连续计算插入的初始节点的后继节点,直到出现以下情况之一:

1. 您已查看树中的所有节点.在这种情况下,您需要插入一个标记此间隔结束的关闭节点.

2. 您会在范围结束后看到关闭节点.在这种情况下,当新范围结束时,您处于现有范围的中间,因此您无需再执行任何操作.你完成了.

3. 您会在范围结束前看到关闭或打开的节点.在这种情况下,您需要从树中删除该节点,因为旧范围包含在新范围内.

4. 您会在范围结束后看到一个打开的节点.在这种情况下,将新的关闭节点插入树中,因为您需要在看到此新范围的开始之前终止当前范围.

天真地实现,该算法的运行时间为O(log n + k log n),其中n是间隔的数量,k是在此过程中移除的间隔的数量(因为您必须执行n次删除).但是,您可以使用以下技巧将其加速到O(log n).由于删除过程始终会删除序列中的节点,因此可以使用端点的后继搜索来确定要删除的范围的结尾.然后,您可以通过执行两个树分割操作和一个树连接操作来拼接子范围以从树中移除.在一个合适的平衡树(红黑或张开,例如),这可以在O(log n)的总时间,这是更快如果有很多范围将会得到归入完成.

希望这可以帮助!