Multiple Date range comparison for overlap: how to do it efficiently?

Question

To check for overlap in two different dateranges, {Start1, End1} and {Start2, End2} I am checking:

if ((Start1 <= End2) && (End1 >= Start2))
{
  //overlap exists
}

The question is, what is a good way to compare overlaps if I had let's say five dateranges?.

checking to see if any of them don't overlap each other?

If I have multiple date ranges, how to find if any of these ranges are overlapping?

Answer 1

Check this Algorithm to detect overlapping periods in brief:

Simple check to see if two time periods overlap.

bool overlap = a.start < b.end && b.start < a.end;

Or in your code...

bool overlap = tStartA < tEndB && tStartB < tEndA;

Answer 2

If I'm understanding correctly, you want to answer the question: Are there any two of these ranges that overlap? Sort them according to their left-hand end, and then go through looking to see if 1 overlaps 2, if 2 overlaps 3, etc. If there is any overlap, this will find it. I don't believe there is any way to answer your question for an arbitrary list of intervals without taking at least O(n log n) time, which is what sorting them will cost you.

Alternatively, perhaps you want to answer the question: Are there any two of these ranges that don't overlap? (On the face of it that's what your edited question is asking, but (1) that seems like a strange thing to want and (2) your comment above seems to indicate that it's not what you mean.) To check for this, find the interval with the leftmost right-hand end and the interval with the rightmost left-hand end, and see whether they overlap. (If any two of your intervals don't overlap, these two don't.)