Java 检查列表中范围内每个元素的交集

Question

我有一个代表 range 类的对象列表，例如

public class Range
{
int upperValue;
int lowerValue
}

然后我有

List<Range> ranges=new ArrayList<>();

在用值填充此列表之后或同时，我想检查插入的每个新范围是否与列表中以前的值相交。

例如，如果我有

[1,4]
[2,4]
[3,5]

我想检测 [3,5] 与 [1,4] 和 [2,4] 相交

并且 [2,4] 与 [1,4] 相交

所以我设法做但效率不高的是:

首先，我使用比较器按较低值对列表进行排序。

然后我在排序后再次循环到列表中，并从列表中的第二个元素开始检查它是​​否与列表中的所有先前元素相交，例如以相反的方式循环。

类似这样的事情

Map<Range,List<Range>> rangeIntersectionMap=new HashMap<>();
for(int i=0;i<ranges.size();i++)
{
if(i>0)
{
List<Range> intersections= rangeIntersectionMap.get(ranges.get(i));
if(intersections==null)
intersections=new ArrayList<>();
for(int j=i-1;j>0;j--)
{
if(checkIntersection(ranges.get(i),ranges.get(j))
{
intersections.add(ranges.get(j));
}
}
rangeIntersectionMap.put(ranges.get(i),intersections);
}
}

这可能意味着，如果我有一个包含 20 个元素的列表，我需要阶乘时间复杂度来检查哪些元素彼此相交。

我认为 NavigableMap 可以解决这个问题，但是我无法正确使用它来实现此目的。

还有其他建议的数据结构或算法吗？

Answer 1

有Interval Search Tree此类问题的结构。

想法是:

• 每个节点代表区间，将两个端点保存在一个节点中
• 在每个节点中保存其子树的最大(右)端点值
• 搜索关键字是两者中较小的值

插入:

• 使用低值来导航插入
• 相应地更新子树中的最大值

搜索:

• 如果节点中的区间与查询区间相交，则返回
• 如果左子树为空，则向右走
• 否则如果左子树中的最大值小于搜索到的低值，则向右走
• 否则向左走

您可以查看这个video和 implementation由 Sedgewick 教授和 Kevin Wayne 教授详细解释。