如何在几百万的列表中找到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

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

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

间隔树将做:

在计算机科学中,间隔树是用于保持间隔的树数据结构.具体而言,它允许人们有效地找到与任何给定间隔或点重叠的所有间隔.它通常用于窗口查询,例如,查找矩形视口内的计算机化地图上的所有道路,或查找三维场景内的所有可见元素.类似的数据结构是段树 ...