Сравнение нескольких диапазонов дат для перекрытия: как это сделать эффективно?

Question

Чтобы проверить наложение в двух разных диапазонах дат, {Start1, End1} и {Start2, End2} Я проверяю:

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

Вопрос в том, , как можно сравнить наложения, если быскажем, пять диапазонов дат? .

проверять, не перекрывают ли какие-либо из них друг друга?найти, перекрывает ли какой-либо из этих диапазонов?

Answer 1

Чтобы найти, если все перекрываются

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

, чтобы найти, если все перекрываются

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

Answer 2

Если я правильно понимаю, вы хотите ответить на вопрос: есть ли два из этих диапазонов, которые перекрываются? Сортируйте их в соответствии с их левым концом, а затем просмотрите, не пересекается ли 1 с 2, не пересекается ли с 2 3 и т. Д. Если есть какое-либо перекрытие, это будет найдено. Я не верю, что есть какой-либо способ ответить на ваш вопрос для произвольного списка интервалов, не занимая хотя бы O (n log n) времени, а именно их сортировка будет стоить вам.

В качестве альтернативы, возможно, вы хотите ответить на вопрос: существуют ли какие-либо из этих двух диапазонов, которые не перекрываются? (На первый взгляд, это то, о чем спрашивает ваш отредактированный вопрос, но (1) это кажется странным, и (2) ваш комментарий выше показывает, что это не то, что вы имеете в виду.) Чтобы проверить это, найдите интервал с крайним левым правым концом и интервал с крайним правым левым концом, и посмотрите, перекрываются ли они. (Если любые два из ваших интервалов не перекрываются, эти два не перекрываются.)

Answer 3

Попробуйте это:

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

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

Answer 5

Установите этот флажок Алгоритм обнаружения перекрывающихся периодов вкратце:

Простая проверка, чтобы увидеть, перекрываются ли два периода времени.

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

Или в вашем коде ...

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