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

Question

假设我有一个区间（或范围）列表（例如 10-15、5-7、9-12 ..）。问题是找到重叠的范围子集。当然，我可以为此使用区间树。

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

在上述情况下，（1）和（2）在第二范围内有重叠，在（3）和（1）、（2）之间在第三范围内有重叠。

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

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

score 1 · Accepted Answer

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

{
  int range;
  int intervalFrom;
  int intervalTo;
}

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

score 0 · Accepted Answer

0

区间 [a0, b0] 和 [a1, b1] 重叠当且仅当 min(b1,b0) > max(a1,a0)

于 2016-04-20T00:08:47.393 回答

2 回答 2