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

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 othe开发者_运维知识库r?

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

---

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

---

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

---

Try this:

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

---

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

---

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;

---

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']