重叠区间的合并算法

Question

我一直在寻找一种有效的算法来合并一个动态的间隔数组上的重叠间隔。例如，(开始时间，结束时间)明智，

[(1, 2), (4, 8), (3, 10)]

变成了

[(1, 2), (3, 10)]

合并后，因为(4，8)和(3，10)是重叠的。重叠意味着两个间隔的任何部分共享相同的时刻。

我知道，当给定一个完整数组时，在对启动时间上升顺序(参考资料:极客)上的间隔进行排序之后，可以使用堆栈进行操作。但是，该算法仅在给定数组非动态的情况下才能有效地应用，但对于动态数组而言，该算法是有效的。例如，将经常更新和插入数组间隔，并在每次操作中合并间隔。

Answer 1

动态数组有什么关系？

您仍然希望按排序升序存储值。然后，应该使用相对简单的二进制搜索来查找最近的间隔(基于开始)，然后只需要检查一两个间隔来确定重叠(因为可以保证现有的间隔不重叠)。

您可能面临的挑战是，这种方法根本不是原子的。您需要在进行合并时锁定集合，这可能无法满足频繁的更新/插入要求。但是，通过保持排序，您应该能够降低算法的复杂性。