algorithm - 间隔相交并找到最小间隔

Question

我有一组重叠的间隔 (a,b) 与 <= b => 让我们称之为“A”间隔

和另一组具有 <= b => 的非重叠间隔 (a,b) 让我们称之为“B”间隔

我需要一个“快速”算法来确定 A 中的间隔是多少，其中最小 b 完全在 B 中的任何间隔内。

例如，A =

[1-2]
[1-5]
[1-10]
[1-200]
[15-20]
[16-18]
[18-18]
[210-220]
[218-219]

和 B =

[2-9]
[11-29]
[200-255]

在这种情况下，区间 [15-20]、[16-18]、[18-18]、[210-220] 和 [218-219] 都在 B 区间内。其中，[16-18] 或 [18-18] 的“b”最低，因此这两个间隔中的任何一个都可以。

另外，我对算法的最坏情况感兴趣。也就是说，概率数据结构并不那么有趣。

我一直在研究区间树，但不清楚如何以有效的方式做到这一点。

内存不是问题。

编辑：忘了说：区间是从 0 到 P 的整数。也就是说，[0,P] 是最大的区间。此外，P 通常不是一个“大”数。它可能是 1000。这可能很方便，因为 O(P) 中的算法可能仍然可行。

EDIT2：有了最后一个注释，如果我们为每个数字 [0..P] 存储一个“a”数字堆，则可能使用 O(max(P,log(N)) 算法。需要堆来获取O(1) 中的最大数字。在上面的示例中，每个数字将具有：

0 - {}
1 - {}
2 - {1}
3 - {}
4 - {}
5 - {1}
6 - {}
.
.
.
10 - {1}
18 - {18, 16} -> in a heap, so getting the max is O(1)
20 - {15}
200 - {1}
219 - {218}
220 - {210}

搜索以 B 间隔遍历“允许”的数字。在上面的例子中，通过 2,3,4,5,6,7,8,9,11-29,200-255。这是 O(P)。然后，对于 B 中的每个数字，将堆的最大值与相应区间的“a”进行比较（例如，在“8”中，区间为“2-9”）。由于最大值是在 O(1) 中获得的，因此遍历所有 P 个数是 O(P)。

要添加/修改 B 区间，我们必须遍历所有 P 数字并更新关联的区间，O(P) 也是如此。

要添加/修改 A 间隔，我们必须在堆中添加/修改它，O(log(N)) 也是如此。

如果有人知道更好的算法，请告诉我:)

谢谢

标签： algorithmsortingintervals