algorithm - 查找多个间隔之间的重叠

Question

假设我有一个间隔(或范围)列表(例如 10-15、5-7、9-12..)。问题是找到重叠的范围子集。我当然可以用 Interval tree为此。

我遇到的实际问题是有多个范围。最好用一个例子来解释:

1. 10-15、5-7、9-12
2. 1-2、3-6、14-15
3. 3-5、9-15、10-15

在上面的例子中，(1)和(2)在第二个范围内有重叠，(3)和(1)、(2)在第三个范围内有重叠。

基本上，我需要找到项目列表之间的所有重叠部分。

也许我可以使用 3 个独立的区间树来找出答案。有一个更好的方法吗？

Answer 1

您可以只构建一棵包含所有区间的区间树。您只需要跟踪间隔所属的范围，例如:

{
  int range;
  int intervalFrom;
  int intervalTo;
}

您可以将该结构放入间隔树中并检查是否重叠。当您获得有问题的区间时，您将能够分辨出每个区间属于哪个范围。