How to find 1 or more partially intersecting time-intervals in a list of few million?

Question

I need an idea for an efficient index/search algorithm, and/or data structure, for determining whether a time-interval overlaps zero or more time-intervals in a list, keeping in mind that a complete overlap is a special case of partial overlap . So far I've not not come up with anything fast or elegant...

Consider a collection of intervals with each interval having 2 dates - start, and end.

Intervals can be large or small, they can overlap each other partially, or not at all. In Java notation, something like this:

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

The goal is to efficiently find all intervals which partially intersect a newly-arrived input interval. For c as an ArrayList this could look like...

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;
}

Iterating through the entire list linearly requires too many compares to meet my performance goals. Instead of ArrayList, something better is needed to direct the search, and minimize the number of comparisons.

My best solution so far involves maintaining two sorted lists internally and conducting 4 binary searches and some list iteration for every request. Any better ideas?

---

Editor's Note: Time-intervals are a specific case employing linear segments along a single axis, be that X, or in this case, T (for time).

Answer 1

Interval trees will do:

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...