CODEWITHSUNDEEP
c#timespan
XN16
XN16

Reputation: 5879

Find distinct TimeSpan duration from a list of TimeSpans

I'm having a bit of trouble trying to process a list of TimeSpan objects without having a lot of code which still doesn't seem to cover all eventualities, tbh, I think I've gone a bit code/logic blind now!

I have a list of TimeSpans of which overlaps will likely occur, but I need a list of TimeSpans which have no overlaps, but cover the whole duration of all TimeSpans.

For example (please note, dates are in ddMMyyyy format):

TS1: 01/01/2020 to 01/02/2020 (1 month)
TS2: 01/03/2020 to 01/05/2020 (2 months)
TS3: 01/04/2020 to 01/07/2020 (3 months with a 1 month overlap with TS2)
TS4: 01/10/2020 to 01/12/2020 (2 months)
TS5: 01/09/2020 to 01/01/2021 (4 months with a 2 month overlap with TS4)

So in this case I would expect to get 3 TimeSpans:

TSA: 01/01/2020 to 01/02/2020 (1 month - same as TS1 as there are no overlaps)
TSB: 01/03/2020 to 01/07/2020 (4 months - combination of TS2 and TS3)
TSC: 01/09/2020 to 01/01/2021 (4 months - combination of TS4 and TS5, technically only TS5 as TS4 is fully encompassed by TS5)

I've tried researching an algorithm online, but without any luck.

Any suggestions would be very welcome.

Upvotes: 0

Views: 320

Answers (2)

Marc Gravell
Marc Gravell

Reputation: 1063328

This isn't optimized at all, but semantically you can do this by adding the chunks and looking for overlaps, then merging those overlaps; something like:

using System;
using System.Collections.Generic;
using System.Globalization;

static class P
{

    static void Main()
    {
        var results = new List<(DateTime From, DateTime To)>();

        Add("01/01/2020", "01/02/2020");
        Add("01/03/2020", "01/05/2020");
        Add("01/04/2020", "01/07/2020");
        Add("01/10/2020", "01/12/2020");
        Add("01/09/2020", "01/01/2021");

        // SEE BELOW, IMPORTANT
        results.Sort(); // initial sort
        while (MergeOneOverlap()) { }
        foreach (var range in results)
        {
            Console.WriteLine($"{range.From:dd/MM/yyyy} - {range.To:dd/MM/yyyy}");
        }

        bool MergeOneOverlap()
        {
            for (int i = 0; i < results.Count; i++)
            {
                var x = results[i];
                for (int j = i + 1; j < results.Count; j++)
                {
                    var y = results[j];
                    if (x.Intersects(y))
                    {
                        results[i] = x.Merge(y);
                        results.RemoveAt(j);
                        results.Sort(); // retain sort while making progress
                        return true;
                    }
                }
            }
            return false;
        }
        void Add(string from, string to)
            => results.Add(
                (DateTime.ParseExact(from, "dd/MM/yyyy", CultureInfo.InvariantCulture),
                DateTime.ParseExact(to, "dd/MM/yyyy", CultureInfo.InvariantCulture)));
    }
    static bool ContainsInclusive(this (DateTime From, DateTime To) range, DateTime when)
    => when >= range.From && when <= range.To;

    static bool Intersects(this (DateTime From, DateTime To) x, (DateTime From, DateTime To) y)
        => x.ContainsInclusive(y.From) || x.ContainsInclusive(y.To) || y.ContainsInclusive(x.From) || y.ContainsInclusive(x.To);

    static (DateTime From, DateTime To) Merge(this (DateTime From, DateTime To) x, (DateTime From, DateTime To) y)
        => (x.From < y.From ? x.From : y.From, x.To > y.To ? x.To : y.To);

}

If this is for large amounts of data, you'd have to look into being much smarter to avoid an O(N^3) problem. It may help to merge every add, if that will often keep the number of items down.

It may also be possible to reduce the complexity to O(N^2) and merging purely forwards (i.e. don't break on successful merge), but I haven't applied enough thinking to see about the implications of that. And O(N^2) is still pretty bad.

For large data, using a sorted list may help, so you can do a binary search on the start dates to find the insertion point. That is getting more complex than I care to write here, though.

I'm 95% sure that this is also fine, i.e. O(N^2):

        MergeOverlaps();
        foreach (var range in results)
        {
            Console.WriteLine($"{range.From:dd/MM/yyyy} - {range.To:dd/MM/yyyy}");
        }

        void MergeOverlaps()
        {
            results.Sort();
            for (int i = 0; i < results.Count; i++)
            {
                var x = results[i];
                for (int j = i + 1; j < results.Count; j++)
                {
                    var y = results[j];
                    if (x.Intersects(y))
                    {
                        results[i] = x = x.Merge(y);
                        results.RemoveAt(j--);
                    }
                }
            }
        }

Upvotes: 1

Vilhelm H.
Vilhelm H.

Reputation: 1335

I would suggest to try a brute force search or a depth-first search algorithm.

First you sort the timespans by starting date.

BRUTE FORCE: You try all combinations and score them by overlap/not overlap, and you probably want to score them by how much of the total timespan is covered.

DEPTH-FIRST-SEARCH: Write a recursive algorithm that start by adding the first interval and then add more interval and backtracks whenever an overlap occur.

Upvotes: 0

Related Questions