Continuous Overlapping of Multiple Date Ranges C#

Question

I am working on an algorithm to calculate a continuous overlap of multiple date ranges. It also needs to have a set number of times that it overlaps. For the example image below, I need 3 dates to overlap continuously. The valid overlapping dates would be Aug 20 - Aug 23, as Aug 24 only has 2 overlapping.

I have attempted many approaches including looping through all dates and comparing each one indivually with the next. That code looks like this.

Here is a .net fiddle for better visualization: https://dotnetfiddle.net/x3LfHR#.

    private bool Compare(CompareDate a, CompareDate b)
    {
        DateTime? tStartA = a.ActiveDate;
        DateTime? tEndA = a.ExpireDate;
        DateTime? tStartB = b.ActiveDate;
        DateTime? tEndB= b.ExpireDate;

        bool overlap = (tStartA <= tEndB || tEndB == null) && (tStartB <= tEndA || tEndA == null);

        DateTime? overlapStart = null;
        DateTime? overlapEnd = null;

        if (overlap)
        {
            //Find maximum start date. 
            overlapStart = (tStartA >= tStartB) ? tStartA : tStartB;
            //Find Min End date between the two
            overlapEnd = (tEndA <= tEndB) ? tEndA : tEndB;

            if (overlapStart > this.overlapStart || this.overlapStart == null)
            {
                this.overlapStart = overlapStart;
            }
            if (overlapEnd < this.overlapEnd || this.overlapEnd == null)
            {
                this.overlapEnd = overlapEnd;
            }

However, this approach makes it tricky to figure out continuous overlap dates. I have attempted to use the .Net Time period library at https://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET, but its not relevant in my case. Any help is appreciated.

This appears to be quite similar to [this question](https://stackoverflow.com/q/13513932/215552). Does its answers help you? — Heretic Monkey, Sep 05 '17 at 21:30
Yes, I have used some aspects of that question already to compare 2 dates. However, since this is an continuous overlap of multiple dates, it makes it much more complicated. — aoakeson, Sep 05 '17 at 21:36
I _think_ I understand. You have a set of date ranges. You need to find an aggregate range, and for every date within that range, there must be at least three constituent ranges that overlap. The combination of constituent ranges can vary across the resulting range, but every date must be fully covered by at least three constituent ranges, with no gaps. Is that correct? If so, in your example, Aug 20-22 are satisfied by A, B, and D, while Aug 23 is satisfied by A, C, and D, yes? Assuming all that is correct, what are the inputs to your algorithm, and their data types? — Mike Strobel, Sep 05 '17 at 22:02
It's generally a good idea to reference other questions with similar titles to make it obvious that you've found and rejected them. Others might have marked the two questions as duplicates, since on the surface they appear quite similar. — Heretic Monkey, Sep 05 '17 at 22:02
@MikeStrobel that is a perfect summary, and better than I explained it. That is correct. In this example Aug 20 - 23 are the only dates that have a continuous overlap of 3 dates. I created a slightly modified version on .net fiddle for better review: https://dotnetfiddle.net/x3LfHR# The input is an active and expire datetime. I am currently comparing them one by one. — aoakeson, Sep 05 '17 at 22:31
One thought as I wait for my ferry home: if you start by sorting your list of date ranges (earliest first), then your algorithm only has to search ranges further ahead in the list. — Mike Strobel, Sep 05 '17 at 22:33
Another question: what's your desired output? Do you want to identify _all_ aggregate ranges with three or more overlapping constituents, or just one? If one, then which one? The single longest overlapping range? The earliest overlapping range? — Mike Strobel, Sep 05 '17 at 22:41
I need the single longest overlapping range. However, there can be multiple of these in a single dataset. I can worry about that in future, for now if I can get the single longest overlapping that would be sufficient. — aoakeson, Sep 05 '17 at 22:48
This requires an array-based algorithm - your sample code is good, but at a too atomic level to do the job. Interesting problem, I'll have a think about this and post shortly! — code4life, Sep 06 '17 at 00:26

code4life · Accepted Answer · 2017-09-06T02:21:55.370

OK - LINQ to the rescue!

Note: In order to make the comparison work, you must remove the time component and strictly use the only the date (e.g. DateTime.Date). Based on your requirements, that's exactly how you need to do it, so it shouldn't be a problem.

public List<DateTime> CompareDates(List<DateTime[]> compareRanges, int overlapLevel = 1)
{
    var grouped = compareRanges.SelectMany(r => r).GroupBy(d => d);
    var thresholdMatch = grouped.Where(g => g.Count() >= overlapLevel)
        .Select(g => g.Key)
        .OrderBy(d => d)
        .ToList();

    return thresholdMatch;
}

You can test the logic in a sample console app, using the skeleton code below as an example:

static void Main()
{
    var setA = new[]
    {
        new DateTime(2017, 8, 20),
        new DateTime(2017, 8, 21),
        new DateTime(2017, 8, 22),      
        new DateTime(2017, 8, 23),      
        new DateTime(2017, 8, 24),
    };

    var setB = new[]
    {
        new DateTime(2017, 8, 20),
        new DateTime(2017, 8, 21),
        new DateTime(2017, 8, 22),
    };

    var setC = new[]
    {
        new DateTime(2017, 8, 22),
        new DateTime(2017, 8, 23),
        new DateTime(2017, 8, 24),
        new DateTime(2017, 8, 25),
        new DateTime(2017, 8, 26),
    };

    var setD = new[]
    {
        new DateTime(2017, 8, 20),
        new DateTime(2017, 8, 21),
        new DateTime(2017, 8, 22),
        new DateTime(2017, 8, 23),
    };

    var compareList = new List<DateTime[]>
    {
        setA, setB, setC, setD
    };

    // setting the threshold to 2 will cause 8/24 to be added to the result...
    // setting this to 1 (default) will return all intersections
    // for now, set it to 3, per the question!
    var result = CompareDates(compareList, 3); 
    foreach (var intersectDate in result)
    {
        Console.WriteLine(intersectDate);
    }
}

Hope this helps, I certainly had fun with it!

P.S. I forked your fiddle: https://dotnetfiddle.net/GUzhjh. This contains the modified version of your original program, so you should be able to play around with it a bit.

Thank you for this, I will try it out shortly, and implement it in my program. Gald someone had fun with it anyways. :P — aoakeson, Sep 06 '17 at 02:22
@aoakeson: you should probably look at the fiddle, that one has the full implementation logic, including the creation of date arrays based on your `Dates` object. The example posted here is more for conceptual understanding. — code4life, Sep 06 '17 at 02:36
Like you said, this solution works if DateTime with time is not required. Unfortunately in my case the time is required. — aoakeson, Sep 06 '17 at 19:28
With a few modifications, I was successfully able to get this to work. Thanks so much for your help on this. — aoakeson, Sep 11 '17 at 23:23
Yeah, i was a bit puzzled by your need to be time-aware. If you have a DateTime range that includes all of Aug 22, it overlaps with a DateTime Range that includes a fragment of Aug 22 - such as 11:00 PM, does it not? The only potential consideration might be if you have a range where the fragment is on the tail-end. But in that situation, simply make the array more granular, so that it represents a date+time rather than just date, and once again, find matches. You'd have to conflate the matches into the date-level, if that's what you're ultimately looking at, but that's fairly simply by then.. — code4life, Sep 12 '17 at 14:17

score 0 · Answer 2 · answered Sep 05 '17 at 22:46

Here is a start at an algorithm:

Sort all start and end datetimes, assigning a +1 to every start and -1 to every end.
proceed from interval-start to interval-end, aggregating the period assignments above looking for a +3 value. Note this datetime.
proceed forward until your aggregate value drops below +3.
Voila! (I think.) Remember this one and continue processing.
When a second occurs, then save the longest and discard the other.
Continue until end-interval found; and report result.

Continuous Overlapping of Multiple Date Ranges C#

2 Answers2