Как проверить дату начала и окончания перекрытия из списка элементов

Question

Что у меня есть

Список объектов с Id, DateStart и DateFinish.

[
    {
        Id: 1234567890,
        DateStart: new DateTime(),
        DateFinish: new DateTime(),
    },
    ...
]

Что мне нужно сделать

Iнужно проверить, если ни одна из дат не перекрывает друг друга.Я не уверен, что overlap передает правильное значение здесь, поэтому вот несколько примеров:

Неверный ввод

[
    {
        Id: 1,
        DateStart: new DateTime().AddHours(1),
        DateFinish: new DateTime().AddHours(3),
    },
    {
        Id: 2,
        DateStart: new DateTime().AddHours(2),
        DateFinish: new DateTime().AddHours(4),
    }
]

Этот список перекрываетсяпотому что время идентификатора 2 находится в середине идентификатора 1

Таблица, чтобы показать лучше:

-------------------------------------------------------------
|       1       |       2       |      3      |      4      | 
|   DateStart1  |               | DateFinish1 |             | 
|               |  DateStart2   |             | DateFinish2 |
-------------------------------------------------------------
                   *overlap*       *overlap*

Другие неверные примеры

-------------------------------------------------------------
|       1       |       2       |      3      |      4      | 
|   DateStart1  |               |             | DateFinish1 | 
|               |  DateStart2   | DateFinish2 |             |
-------------------------------------------------------------
                   *overlap*       *overlap*


-------------------------------------------------------------
|       1       |       2       |      3      |      4      | 
|   DateStart1  |               |             | DateFinish1 | // This would be a full overlap 
|   DateStart2  |               |             | DateFinish2 | // And it's also Invalid
-------------------------------------------------------------
    *overlap*                                    *overlap*

-------------------------------------------------------------
|       1       |       2       |      3      |      4      | 
|               |  DateStart1   |             | DateFinish1 | // Same as first example
|  DateStart2   |               | DateFinish2 |             | // But "inverted"
-------------------------------------------------------------
                   *overlap*       *overlap*

ДействительныйЗапись

[
    {
        Id: 1,
        DateStart: new DateTime().AddHours(1),
        DateFinish: new DateTime().AddHours(2),
    },
    {
        Id: 2,
        DateStart: new DateTime().AddHours(2),
        DateFinish: new DateTime().AddHours(4),
    }
]

Таблица, чтобы показать лучше:

-------------------------------------------------------------
|       1       |       2       |      3      |      4      | 
|   DateStart1  |  DateFinish1  |             |             | 
|               |  DateStart2   |             | DateFinish2 |
-------------------------------------------------------------
                  *not overlap*

И вы также можете иметь DateStart и DateFinish, которые имеют то же значение, что означает, что это можетначало и конец одновременно.

-------------------------------------------------------------
|       1       |       2       |      3      |      4      | 
|   DateStart1  |               |             |             | 
|   DateFinish1 |               |             |             | 
|   DateStart2  |               |             | DateFinish2 |
-------------------------------------------------------------
  *not overlap*

То, что я сделал до сих пор:

Я делаю цикл foreach, который item является каждым элементом, и использую гдесо следующим выражением:

myList.Any(
    x => x.Id == item.Id 
        &&
    (
        (
            item.DateStart <= x.DateStart 
                && 
            item.DateFinish > x.DateStart 
                && 
            item.DateFinish <= x.DateFinish
        ) 
            ||
        (
            item.DateStart >= x.DateStart 
                && 
            item.DateStart < x.DateFinish 
                && 
            item.DateFinish > x.DateFinish
        ) 
            ||
        (
            item.DateStart <= x.DateStart 
                && 
            item.DateFinish >= x.DateFinish
        )
    ) 
)

Мой вопрос

Правильно ли это выражение?Я пробовал это с большим количеством данных, и иногда кажется, что это неправильно.

Я должен быть уверен, что это охватит все крайние случаи.

Если есть лучший способ записи всехэта логика, это помогло бы, потому что этот код выглядит уродливым и трудным для понимания другими людьми.

Answer 1

Я пытался отразить ваши случаи, но я бы посоветовал написать модульные тесты для полного тестирования всех ваших сценариев.

List<FooBar> bars = new List<FooBar>()
    {
        new FooBar() //end date is inside 3
        {
            Start = new DateTime(2001,12,1),
            End = new DateTime(2002,5,15),
            Id = 1
        },
        new FooBar() //fine
        {
            Start = new DateTime(2005,12,1),
            End = new DateTime(2006,5,15),
            Id = 2
        },
        new FooBar() //start date is inside 1
        {
            Start = new DateTime(2002,4,1),
            End = new DateTime(2003,5,15),
            Id = 3
        },
        new FooBar() //this one is fine
        {
            Start = new DateTime(2006,5,15),
            End = new DateTime(2007,5,15),
            Id = 4
        },
        new FooBar() //also fine
        {
            Start = new DateTime(2001,12,1),
            End = new DateTime(2001,12,1),
            Id = 5
        },
    };

А потом, по крайней мере мне, немного легче читать / просматривать фрагмент кода, который, кажется, отлично работает:

 var inside = bars.Where(w => 
        bars.Where(outer => ((outer.Start < w.Start && outer.End > w.Start)
            || (outer.Start < w.End && outer.End > w.End)
            || (outer.Start == w.Start && outer.End == w.End)) && outer.Id != w.Id).Any()).ToList();

    inside.ForEach(e => {
        Console.WriteLine($"{e.Id}");
    });

Для реального использования я бы также протестировалдля Any или First, а не ToList, но это дает мне идентификаторы для проверки консоли.

Что касается того, почему я использовал эту логику, она может оказаться ошибочной, но мои предположения:

An перекрывается дата начала находится между началом и концом другого ввода, либо дата окончания элемента находится между датами начала и конца другого ввода, либо дата начала и окончания точно совпадает со значениями другого ввода.

Дополнительнотесты (как с предоставленным вами кодом) я ожидаю ложные срабатывания из-за использования <= и> =

Например, изменение метода на

bars.Where(outer => ((outer.Start <= w.Start && outer.End >= w.Start)

дает мне ложные срабатывания на 4 и 5

Answer 2

Я бы использовал следующий код:

static bool IsOverlapping(IEnumerable<Range> list)
{
    Range previousRange = null;
    foreach (var currentRange in list.OrderBy(x => x.DateStart).ThenBy(x => x.DateFinish))
    {
        if (currentRange.DateStart > currentRange.DateFinish)
            return true;

        if (previousRange?.DateFinish > currentRange.DateStart)
            return true;

        previousRange = currentRange;
    }

    return false;
}

Answer 3

Быстрая и грязная версия.Не очень производительный, как на больших наборах.Но можно улучшить.

https://dotnetfiddle.net/Widget/PEn2Lm

    static void DetectOverlap(List<Range> l)
    {
        foreach(var r in l)
        {
            var overlap = l.Any(x => x.Id != r.Id 
                  && ((r.Start == x.Start && r.End == x.End) 
                      || (r.Start >= x.Start && r.Start < x.End)
                      || (r.End > x.Start && r.End <= x.End)));
            if(overlap)
            {
                Console.WriteLine("Overlap detected");
                throw new Exception("Overlapping range detected");
            }
        }
        Console.WriteLine("Clean ranges");
    }