Get contiguous date ranges

Question

Given a list of date ranges, I'd like to get a list of contiguous date ranges.

I'm not too sure of the terminology of what I'm looking for, but I've put together a skeleton:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace ContiguousTimeSpans
{
    class Program
    {
        static void Main(string[] args)
        {
            List<DateRange> ranges = new List<DateRange>();
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 07:00:00"), DateTime.Parse("01/12/2015 10:00:00")));
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 06:00:00"), DateTime.Parse("01/12/2015 09:00:00")));
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 05:00:00"), DateTime.Parse("01/12/2015 08:00:00")));
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 18:00:00"), DateTime.Parse("01/12/2015 21:00:00")));
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 12:00:00"), DateTime.Parse("01/12/2015 14:00:00")));
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 20:00:00"), DateTime.Parse("01/12/2015 22:00:00")));
            ranges.Add(new DateRange(DateTime.Parse("01/12/2015 11:00:00"), DateTime.Parse("01/12/2015 23:00:00")));

            List<DateRange> contiguousBlocks = GetContiguousTimespans(ranges);
            Debug.Assert(contiguousBlocks.Count == 2);

            Debug.Assert(contiguousBlocks[0].Start.Hour == 5);
            Debug.Assert(contiguousBlocks[0].End.Hour == 10);

            Debug.Assert(contiguousBlocks[1].Start.Hour == 11);
            Debug.Assert(contiguousBlocks[1].End.Hour == 23);

            Console.ReadKey();
        }

        public static List<DateRange> GetContiguousTimespans(List<DateRange> ranges)
        {
            List<DateRange> result = new List<DateRange>();
            //???
            return result;
        }
    }

    public class DateRange
    {
        public DateTime Start { get; set; }
        public DateTime End { get; set; }

        public DateRange(DateTime start, DateTime end)
        {
            Start = start;
            End = end;
        }
    }
}

Is there a way to deduce the contiguous ranges?

Fertile

so what's your question.. what's the problem and or issue with your existing code..? what happens when you run the code..? – Dissolve

Hi MethodMan, I don't know the algorithm to implement in GetContiguousTimespans(). The attempt I've made is messy and I don't want to pollute the skeleton – Fertile

No my attempt didn't work, hence the question on SO. I'm sure someone on SO has encountered a similar problem before. – Fertile

One suggestion is to sort by the start time first; this may make it easier to think about how to combine them together. – Blur

check this posting .. sounds like something similar #19433689 – Dissolve

Have a look at Time Period Library for .NET – Whirligig

Answer 1

Not sure I understand this completely, but regarding what is written and the test data this should work:

public static List<DateRange> GetContiguousTimespans(List<DateRange> ranges)
{
    List<DateRange> result = new List<DateRange>();
    ranges.Sort((a,b)=>a.Start.CompareTo(b.Start));
    DateRange cur = ranges[0];

    for (int i = 1; i < ranges.Count; i++)
    {
        if (ranges[i].Start <= cur.End)
        {
            if (ranges[i].End >= cur.End)
                cur.End = ranges[i].End;
        }
        else
        {
            result.Add(cur);
            cur = ranges[i];
        }
    }

    result.Add(cur);

    return result;
}

Of course this also will need to add some checks for border values, but general idea should be clear I guess.

Ancestral

note : you dont need to check ranges[i].Start >= cur.Start because you already sorted ranges by start before. – Naucratis

You are right - this part of expression is always true ) It stays there from a previous version. But from the other hand it's a bit easier to understand what's going on with this condition ) Anyway, thanks! – Ancestral

That's quite nice Magister, thank you for algorithm! – Fertile

You do know that this modifies the original ranges list? – Hurley

Answer 2

So if I start with this input:

List<DateRange> ranges = new List<DateRange>()
{
    new DateRange(DateTime.Parse("01/12/2015 07:00:00"), DateTime.Parse("01/12/2015 10:00:00")),
    new DateRange(DateTime.Parse("01/12/2015 06:00:00"), DateTime.Parse("01/12/2015 09:00:00")),
    new DateRange(DateTime.Parse("01/12/2015 05:00:00"), DateTime.Parse("01/12/2015 08:00:00")),
    new DateRange(DateTime.Parse("01/12/2015 18:00:00"), DateTime.Parse("01/12/2015 21:00:00")),
    new DateRange(DateTime.Parse("01/12/2015 12:00:00"), DateTime.Parse("01/12/2015 14:00:00")),
    new DateRange(DateTime.Parse("01/12/2015 20:00:00"), DateTime.Parse("01/12/2015 22:00:00")),
    new DateRange(DateTime.Parse("01/12/2015 11:00:00"), DateTime.Parse("01/12/2015 23:00:00")),
};

Then this works for me:

var ordered = ranges.OrderBy(x => x.Start).ThenBy(x => x.End).ToArray();

var working =
    ordered
        .Skip(1)
        .Aggregate(new
        {
            contiguous = new List<DateRange>(),
            current = ordered.First(),
        }, (a, r) =>
        {
            if (a.current.End >= r.Start)
            {
                return new
                {
                    a.contiguous,
                    current = r.End > a.current.End
                        ? new DateRange(a.current.Start, r.End)
                        : a.current,
                };
            }
            else
            {
                a.contiguous.Add(a.current);
                return new
                {
                    a.contiguous,
                    current = r,
                };
            }
        });

var results = working.contiguous;
results.Add(working.current);

The final result I get is this:

Hurley

Answer 3

Thank you Kiwi. I've looked at the Time Period Library and it has a feature called 'Time Period Combiner' which is exactly what I was looking for.

And the code to use it in my case was:

public static List<DateRange> GetContiguousTimespans(List<DateRange> ranges)
{
    //convert my DateRange objects into the objects used by the Time Period Library
    TimePeriodCollection periods = new TimePeriodCollection();
    ranges.ForEach(ts => periods.Add(new TimeRange(ts.Start, ts.End)));

    //get a list of contiguous date ranges
    TimePeriodCombiner<TimeRange> periodCombiner = new TimePeriodCombiner<TimeRange>();
    ITimePeriodCollection combinedPeriods = periodCombiner.CombinePeriods(periods);

    //convert the objects back to DateRanges
    List<DateRange> result = combinedPeriods.Select(cp => new DateRange(cp.Start, cp.End)).ToList();
    return result;
}

Fertile