'How to validate Date Start and Finish Overlap from a list of items
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.
Solution 1:[1]
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;
}
Solution 2:[2]
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");
}
Solution 3:[3]
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
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | Sai Puli |
| Solution 3 | Austin T French |