Compare Intervals (JodaTime) in a list for overlap

问题:

I have a list of intervals, and I need to compare them for overlaps.

List<Interval> intervals = new ArrayList<>();
intervals.add(new Interval(dateTime1, dateTime2));
intervals.add(new Interval(dateTime3, dateTime4));
intervals.add(new Interval(dateTime5, dateTime6));

eg. dateTime1 = 2014-06-01 dateTime2 = 2014-07-01

dateTime3 = 2014-08-01 dateTime4 = 2014-09-01

dateTime5 = 2014-08-15 dateTime6 = 2014-09-15

In this case, there is an overlap between the 2nd and the 3rd interval. I can use the Interval.overlaps method to find that. I'm thinking of 2 for loops and going through each of the intervals in the list to compare. But that solution is O(n*n). What is a more efficient way to do this?

回答1:

You should first sort the intervals by start time in ascending order and then apply only one for-loop to find out which intervals are overlapping.

When using the single for-loop-solution you need to compare TWO neighbour intervals if they overlap or not. Of course you have to check the range condition of the loop, too, to pay attention for that you consider two intervals per single loop run. Something like this (not tested):

public boolean isOverlapping(List<Interval> sortedIntervals) {
  for (int i = 0, n = sortedIntervals.size(); i < n - 1; i++) {
    if (sortedIntervals.get(i).overlaps(sortedIntervals.get(i + 1))) {
      return true; // your evaluation for overlap case
    }
  }

  return false;
}