java - 如何在几百万个列表中找到 1 个或多个部分相交的时间间隔？

Question

我需要一个高效的索引/搜索算法和/或数据结构的想法，以确定时间间隔是否与列表中的零个或多个时间间隔重叠，请记住完全重叠是一种特殊情况部分重叠。到目前为止，我还没有想出任何快速或优雅的东西......

考虑一组间隔，每个间隔有 2 个日期 - 开始和结束。

间隔可大可小，可以部分重叠，也可以完全不重叠。在 Java 表示法中，是这样的:

interface Period 
{
  long getStart(); // millis since the epoch
  long getEnd();
  boolean intersects(Period p); // trivial intersection check with another period
}

Collection<Period> c = new ArrayList<Period>(); // assume a lot of elements

目标是有效地找到与新到达的输入区间部分相交的所有区间。对于作为 ArrayList 的 c，这可能看起来像...

Collection<Period> getIntersectingPeriods(Period p)
{
  // how to implement this without full iteration?
  Collection<Period> result = new ArrayList<Period>();
  for (Period element : c)
    if (element.intersects(p))
      result.add(element);
  return result;
}

线性遍历整个列表需要太多比较才能满足我的性能目标。需要更好的东西来代替 ArrayList 来指导搜索，并最大限度地减少比较次数。

到目前为止，我最好的解决方案是在内部维护两个排序列表，并对每个请求进行 4 次二进制搜索和一些列表迭代。有更好的想法吗？

---

编者注:时间间隔是沿单个轴使用线性段的特定情况，即 X，或在本例中为 T(时间)。

Answer 1

Interval trees会做:

In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree...