Calculating number of nights in overlapping dates

Question

I'm having an issue figuring out a logical way to solve this problem. I have a list of date ranges, say for example:

01/01/15 - 11/01/15 
02/01/15 - 04/01/15 
09/01/15 - 13/01/15 
18/01/15 - 20/01/15

What I need to do is figure out the total number of nights covered over all of these date ranges.

So for the example the total should be 14 nights:

01/01/15 - 11/01/15 // 10 nights
02/01/15 - 04/01/15 // Ignored as nights are covered in 1-11
09/01/15 - 13/01/15 // 2 nights as 11th and 12th nights haven't been covered
18/01/15 - 20/01/15 // 2 nights

I can easily figure out the total number of nights using min-max dates but that ignores the missing dates (14-17 in the example) and is what I can't figure out.

Is there any way to find the total number of days missing to help figure this out?

Answer 1

Here's a way using a HashSet:

public static int CountDays(IEnumerable<TimeRange> periods)
{
    var usedDays = new HashSet<DateTime>();

    foreach (var period in periods)
        for (var day = period.Start; day < period.End; day += TimeSpan.FromDays(1))
            usedDays.Add(day);

    return usedDays.Count;
}

This assumes that your date ranges are half-open intervals (i.e. the start date is considered part of the range but the end date is not).

Here's a complete program to demonstrate. The answer is 14:

using System;
using System.Collections.Generic;

namespace ConsoleApplication2
{
    public sealed class TimeRange
    {
        public DateTime Start { get; private set; }
        public DateTime End   { get; private set; }

        public TimeRange(string start, string end)
        {
            Start = DateTime.Parse(start);
            End   = DateTime.Parse(end);
        }
    }

    internal class Program
    {
        public static void Main()
        {
            var periods = new []
            {
                new TimeRange("01/01/15", "11/01/15"), 
                new TimeRange("02/01/15", "04/01/15"),
                new TimeRange("09/01/15", "13/01/15"),
                new TimeRange("18/01/15", "20/01/15")
            };

            Console.WriteLine(CountDays(periods));
        }

        public static int CountDays(IEnumerable<TimeRange> periods)
        {
            var usedDays = new HashSet<DateTime>();

            foreach (var period in periods)
                for (var day = period.Start; day < period.End; day += TimeSpan.FromDays(1))
                    usedDays.Add(day);

            return usedDays.Count;
        }
    }
}

NOTE: This is NOT very efficient for large date ranges! If you have large date ranges to consider, an approach that combines overlapping ranges into single ranges would be better.

[EDIT] Fixed the code to use half-open intervals rather than closed intervals.

Answer 2

Something like this should work:

internal class Range
{
    internal DateTime From, To;

    public Range(string aFrom, string aTo)
    {
        From = DateTime.ParseExact(aFrom, "dd/mm/yy", CultureInfo.InvariantCulture);
        To = DateTime.ParseExact(aTo, "dd/mm/yy", CultureInfo.InvariantCulture);
    }
}

    public static int ComputeNights(IEnumerable<Range> ranges)
    {
        var vSet = new HashSet<DateTime>();
        foreach (var range in ranges)
            for (var i = range.From; i < range.To; i = i.AddDays(1)) vSet.Add(i)
        return vSet.Count;
    }

The code to run your example:

        var vRanges = new List<Range>
        {
            new Range("01/01/15", "11/01/15"),
            new Range("02/01/15", "04/01/15"),
            new Range("09/01/15", "13/01/15"),
            new Range("18/01/15", "20/01/15"),
        };
        var v = ComputeNights(vRanges);

v evaluates to 14

Answer 3

You could calculate it like this:

var laterDateTime = Convert.ToDateTime("11/01/15 ");
var earlierDateTime = Convert.ToDateTime("01/01/15");

TimeSpan dates = laterDateTime - earlierDateTime;

int nights = dates.Days - 1;

you could convert whatever you have into DateTime. Then you can subtract both DateTimes with the - operator. Your result will be a type of struct TimeSpan.

TimeSpan hat a Days property. Substract 1 from that and you recieve the nights.

between 2 Days is 1 Night
between 3 Days are 2 Nights
between 4 Days are 3 Nights

I am sure you can do the rest.

Answer 4

Just in case you didn't have enough answers here is one more using Linq and Aggregate. Returns 14 nights.

List<Tuple<DateTime, DateTime>> dates = new List<Tuple<DateTime, DateTime>>
    {
        Tuple.Create(new DateTime(2015, 1,1), new DateTime(2015, 1,11)),
        Tuple.Create(new DateTime(2015, 1,2), new DateTime(2015, 1,4)),
        Tuple.Create(new DateTime(2015, 1,9), new DateTime(2015, 1,13)),
        Tuple.Create(new DateTime(2015, 1,18), new DateTime(2015, 1,20))
    };

    var availableDates = 
          dates.Aggregate<Tuple<DateTime, DateTime>, 
                          IEnumerable<DateTime>, 
                          IEnumerable<DateTime>>
                (new List<DateTime>(),
                (allDates, nextRange) => allDates.Concat(Enumerable.Range(0, (nextRange.Item2 - nextRange.Item1).Days)
                                                 .Select(e => nextRange.Item1.AddDays(e))),
                 allDates => allDates);


    var numDays = 
          availableDates.Aggregate<DateTime, 
                                  Tuple<DateTime, int>, 
                                  int> 
                         (Tuple.Create(DateTime.MinValue, 0),                                                                                               
                         (acc, nextDate) =>
                         {
                             int daysSoFar = acc.Item2;                                                                                    
                             if ((nextDate - acc.Item1).Days == 1)                                                                                                
                             {                                                                                      
                                daysSoFar++;                                                                                                                                                                
                             }                                                                                                                                                                                                                                                                                                                        

                             return Tuple.Create(nextDate, daysSoFar);                                                                          
                          },
                          acc => acc.Item2);

Answer 5

I think this solution will be faster then looping through ranges with inner loop for inserting days in list. This solution doesn't requires additional space. It is O(1) and it loops through ranges only once so it's complexity is O(n). But it assumes that your ranges are ordered by startdate. If not you can always order them easily:

var p = new[]
{
    new Tuple<DateTime, DateTime>(DateTime.ParseExact("01/01/15", "dd/MM/yy", CultureInfo.InvariantCulture), DateTime.ParseExact("11/01/15", "dd/MM/yy", CultureInfo.InvariantCulture)),
    new Tuple<DateTime, DateTime>(DateTime.ParseExact("02/01/15", "dd/MM/yy", CultureInfo.InvariantCulture), DateTime.ParseExact("04/01/15", "dd/MM/yy", CultureInfo.InvariantCulture)),
    new Tuple<DateTime, DateTime>(DateTime.ParseExact("09/01/15", "dd/MM/yy", CultureInfo.InvariantCulture), DateTime.ParseExact("13/01/15", "dd/MM/yy", CultureInfo.InvariantCulture)),
    new Tuple<DateTime, DateTime>(DateTime.ParseExact("18/01/15", "dd/MM/yy", CultureInfo.InvariantCulture), DateTime.ParseExact("20/01/15", "dd/MM/yy", CultureInfo.InvariantCulture))
};

int days = (p[0].Item2 - p[0].Item1).Days;
var endDate = p[0].Item2;

for(int i = 1; i < p.Length; i++)
{
    if(p[i].Item2 > endDate)
    {
        days += (p[i].Item2 - (p[i].Item1 > endDate ? p[i].Item1 : endDate)).Days;
        endDate = p[i].Item2;
    }
}

Answer 6

Assuming there are two nights between e.g. Jan 1 and Jan 3, this should work. If you already have DateTime values instead of string, you can get rid of the parsing bit. Basically, I'm using DateTime.Subtract() to calculate the number of days (i.e. nights) between two dates.

namespace DateTest1
{
    using System;
    using System.Collections.Generic;
    using System.Globalization;

    class Program
    {
        static void Main(string[] args)
        {
            var intervals = new List<Tuple<string, string>>
                                {
                                    new Tuple<string, string>("01/01/15", "11/01/15"),
                                    new Tuple<string, string>("02/01/15", "04/01/15"),
                                    new Tuple<string, string>("09/01/15", "13/01/15"),
                                    new Tuple<string, string>("18/01/15", "20/01/15")
                                };

            var totalNights = 0;

            foreach (var interval in intervals)
            {
                var dateFrom = DateTime.ParseExact(interval.Item1, "dd/MM/yy", CultureInfo.InvariantCulture);
                var dateTo = DateTime.ParseExact(interval.Item2, "dd/MM/yy", CultureInfo.InvariantCulture);

                var nights = dateTo.Subtract(dateFrom).Days;

                Console.WriteLine("{0} - {1}: {2} nights", interval.Item1, interval.Item2, nights);

                totalNights += nights;
            }

            Console.WriteLine("Total nights: {0}", totalNights);
        }
    }
}

---

01/01/15 - 11/01/15: 10 nights
02/01/15 - 04/01/15: 2 nights
09/01/15 - 13/01/15: 4 nights
18/01/15 - 20/01/15: 2 nights
Total nights: 18
Press any key to continue . . .