algorithm - 以间隔合并范围

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)。由于删除过程总是按顺序删除节点，您可以使用后续搜索端点来确定要删除的范围的末尾。然后，您可以通过执行两次树拆分操作和一次树连接操作来拼接子范围以从树中移除。在合适的平衡树(例如红黑树或 splay 树)上，这可以在 O(log n) 总时间内完成，如果要包含很多范围，这会快得多。

希望这对您有所帮助!