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?

Sheri

Do you need to know if they all overlap in 1 spot or if any of them don't overlap each other? – Domicile

Please clarify your question. What do you mean by "compare overlaps"? – Kareykari

@Yuriy Faktorovich, @gaearon: Guys, I edited the question. Basically, I just want to know whether an overlap exists of not, if I had multiple date ranges in any order. – Sheri

Answer 1

To find if all are overlapping

static bool Overlap(params Tuple<DateTime, DateTime>[] ranges)
{
    for (int i = 0; i < ranges.Length; i++)
    {
        for (int j = i + 1; j < ranges.Length; j++)
        {
            if (!(ranges[i].Item1 <= ranges[j].Item2 && ranges[i].Item2 >= ranges[j].Item1))
                return false;

        }
    }
    return true;
}

to find if any are overlapping

static bool Overlap(params Tuple<DateTime, DateTime>[] ranges)
{
    for (int i = 0; i < ranges.Length; i++)
    {
        for (int j = i + 1; j < ranges.Length; j++)
        {
            if (ranges[i].Item1 <= ranges[j].Item2 && ranges[i].Item2 >= ranges[j].Item1)
                return true;

        }
    }
    return false;
}

Domicile

isn't this n^2 while sorting will have n log(n) ? – Known

@Known I wasn't sure if - 1 would be more efficient than just letting it do an extra compare. – Domicile

@Known I'm not sure what there is to sort on, can you explain? – Domicile

@Yuriy - sorting solution is explained in Gareth's answer (1st part) – Known

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

Berton

very clever solutions for both problems. – Vaduz

For anyone needing to perform more complex times of overlap checking, there is a data structure called Interval Tree. en.wikipedia.org/wiki/Interval_tree – Vaduz

@Gareth, I'm a non native-english speaker, could u please explain what left-hand end and right-hand end mean? – Thrive

Left-hand = start = earliest time. Right-hand = end = latest time. – Berton

Answer 3

Try this:

    private bool intersects(DateTime r1start, DateTime r1end, 
                            DateTime r2start, DateTime r2end)
    {
        return (r1start == r2start) 
            || (r1start > r2start ? 
                r1start <= r2end : r2start <= r1end);
    }

Enthrone

Answer 4

   DateTime h1 = historyRecord.serviceStartDate;
   DateTime h2 = historyRecord.serviceEndDate;
   DateTime r1 = record.serviceStartDate;
   DateTime r2 = record.serviceEndDate;
   if (!((h1 > r1 && h1 > r2 && h2 > r1 && h2 > r2) || 
        (h1 < r1 && h1 < r2 && h2 < r1 && h2 < r2)))
       {
         count += 1;
       }

Voltmeter

Answer 5

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;

Trend

Answer 6

To complement Gareth answer. For anyone needing to perform more complex types of overlap checking in intervals, there is a nice data structure called Interval Tree.

https://en.wikipedia.org/wiki/Interval_tree

tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.

Example taken from this javascript implementation

let tree = new IntervalTree();

let intervals = [[6,8],[1,4],[5,12],[1,1],[5,7]];

// Insert interval as a key and string "val0", "val1" etc. as a value 
for (let i=0; i < intervals.length; i++) {
    tree.insert(intervals[i],"val"+i);
}

// Get array of keys sorted in ascendant order
let sorted_intervals = tree.keys;              //  expected array [[1,1],[1,4],[5,7],[5,12],[6,8]]

// Search items which keys intersect with given interval, and return array of values
let values_in_range = tree.search([2,3])  //  expected array ['val1']

Vaduz