How to validate Date Start and Finish Overlap from a list of items

Question

What I have

A list of objects with Id, DateStart and DateFinish.

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

What I need to do

I need to validate if none of the dates overlap each other. I'm not sure if overlap is passing the right meaning here, so here is some examples:

Invalid Entry

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

This list have an overlap because the time of id 2 is in the middle of id 1

A table to show better:

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

Other Invalid Examples

-------------------------------------------------------------
|       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*

Valid Entry

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

A table to show better:

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

And you can also have DateStart and DateFinish that are the same value, which means it can start and end at the same time.

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

What I have done so far:

I'm making a foreach loop, where item is each element, and using a where with the following expression:

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

My Question

Is this expression correct? I have tried it with a lot of data and it seems to be wrong sometimes.

I need to be certain that it will cover all edge cases.

If there is a better way of writing all this logic, it would help to, because this code looks to ugly and hard to understand for other people.

Answer 1

A quick and dirty version. Not very performant as is on large sets. But can be improved on.

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

Answer 2

I tried to mirror your cases, but I'd suggest writing unit tests to full test all of your scenarios.

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

And then a, to me at least, slightly easier to read / skim code snippet which seems to work perfectly:

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

For actual use, I'd also test for Any or First, and not ToList, but this gives me the Ids for the console to check.

As for why I used this logic, it might prove faulty but my assumptions:

An overlapped start date is between another input's start and end, or an item's end date is between another input's start and end dates, or a start and end date matches another input's values exactly.

Additional tests (as with your provided code) I expect false positives due to the use of <= and >=.

For example, changing the method to include

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

gives me false positives on 4 and 5

Answer 3

I would use the following code:

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