Determine which part of an interval overlaps a given weekday in a given time zone

I have a global time interval (from one UTC "time stamp" to another) and want to determine which part of the interval overlaps a given week day in a given time zone.

Let's take an example: say the interval is 2018-05-11T02:00:00Z/2018-05-11T10:00:00Z and the day of week is Friday.

For New York (America/New_York), the interval translates into the local date time interval 2018-05-10T22:00/2018-05-11T06:00, where the first two hours of the interval don't overlap Friday. The resulting interval should therefore be 2018-05-11T04:00:00Z/2018-05-11T10:00:00Z. Had the time zone been Copenhagen (Europe/Copenhagen), the original interval would remain unchanged, since all of it overlaps Friday in that time zone.

If the interval had been long enough, you could easily have multiple overlaps with the week day. Having no overlaps at all is of course also a possibility.

I'm having a hard time figuring out the best and most reliable way to solve this. My best idea is to take the day of week and translate it into global time from the given time zone and then check for overlaps. However, a day of week isn't anchored to a specific date, which means I don't really have anything to translate, and would therefore first have to figure out what potentially overlapping dates the day of week would be.

If I translate the interval into local time, take the overlap with the day of week (much easier, because I now have actual dates to work with) and then translate them back, I would get the right answer in most cases. However, things like DST transitions could easily mess things up, when translating back, and fall back could cause the local date time interval to be "invalid", i.e. start is after end, opening another can of worms.

I'm trying to solve the problem in C# with NodaTime, but think the problem is a general one.

Below is a couple of test cases as requested by @jskeet:

using FluentAssertions;
using NodaTime;
using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;

public class Tests
{
    public static TheoryData<Interval, IsoDayOfWeek, DateTimeZone, IEnumerable<Interval>> OverlapsDayOfWeekExamples = new TheoryData<Interval, IsoDayOfWeek, DateTimeZone, IEnumerable<Interval>>
    {
        {   // No overlap in given time zone
            new Interval(Instant.FromUtc(2018, 05, 11, 00, 00), Instant.FromUtc(2018, 05, 11, 04, 00)),
            IsoDayOfWeek.Friday,
            DateTimeZoneProviders.Tzdb["America/New_York"],
            Enumerable.Empty<Interval>()
        },
        {   // Cut short because interval begins Thursday
            new Interval(Instant.FromUtc(2018, 05, 11, 02, 00), Instant.FromUtc(2018, 05, 11, 10, 00)),
            IsoDayOfWeek.Friday,
            DateTimeZoneProviders.Tzdb["America/New_York"],
            new [] { new Interval(Instant.FromUtc(2018, 05, 11, 04, 00), Instant.FromUtc(2018, 05, 11, 10, 00)) }
        },
        {   // Remains unchanged because everything overlaps in given time zone
            new Interval(Instant.FromUtc(2018, 05, 11, 02, 00), Instant.FromUtc(2018, 05, 11, 10, 00)),
            IsoDayOfWeek.Friday,
            DateTimeZoneProviders.Tzdb["Europe/Copenhagen"],
            new [] { new Interval(Instant.FromUtc(2018, 05, 11, 02, 00), Instant.FromUtc(2018, 05, 11, 10, 00)) }
        },
        {   // Cut short because interval begins Saturday and day starts at 01:00 (Spring forward)
            new Interval(Instant.FromUtc(2018, 11, 04, 02, 15), Instant.FromUtc(2018, 11, 04, 06, 30)),
            IsoDayOfWeek.Sunday,
            DateTimeZoneProviders.Tzdb["America/Sao_Paulo"],
            new [] { new Interval(Instant.FromUtc(2018, 11, 04, 03, 00), Instant.FromUtc(2018, 11, 04, 06, 30)) }
        },
        {   // Cut short because interval begins Saturday and day starts later (Fall back)
            new Interval(Instant.FromUtc(2018, 02, 18, 01, 00), Instant.FromUtc(2018, 02, 18, 07, 30)),
            IsoDayOfWeek.Sunday,
            DateTimeZoneProviders.Tzdb["America/Sao_Paulo"],
            new [] { new Interval(Instant.FromUtc(2018, 02, 18, 03, 00), Instant.FromUtc(2018, 02, 18, 07, 30)) }
        },
        {   // Overlaps multiple times (middle overlap is during DST transition)
            new Interval(Instant.FromUtc(2018, 10, 28, 16, 15), Instant.FromUtc(2018, 11, 11, 12, 30)),
            IsoDayOfWeek.Sunday,
            DateTimeZoneProviders.Tzdb["America/New_York"],
            new []
            {
                new Interval(Instant.FromUtc(2018, 10, 28, 16, 15), Instant.FromUtc(2018, 10, 29, 04, 00)),
                new Interval(Instant.FromUtc(2018, 11, 04, 04, 00), Instant.FromUtc(2018, 11, 05, 05, 00)),
                new Interval(Instant.FromUtc(2018, 11, 11, 05, 00), Instant.FromUtc(2018, 11, 11, 12, 30)),
            }
        },
        {   // Results in an invalid date time interval
            new Interval(Instant.FromUtc(2018, 10, 28, 00, 45), Instant.FromUtc(2018, 10, 28, 01, 15)),
            IsoDayOfWeek.Sunday,
            DateTimeZoneProviders.Tzdb["Europe/Copenhagen"],
            new [] { new Interval(Instant.FromUtc(2018, 10, 28, 00, 45), Instant.FromUtc(2018, 10, 28, 01, 15)) }
        },
    };

    [Theory]
    [MemberData(nameof(OverlapsDayOfWeekExamples))]
    public void OverlapsDayOfWeekTest531804504(Interval interval, IsoDayOfWeek dayOfWeek, DateTimeZone timeZone, IEnumerable<Interval> expected)
    {
        OverlapsDayOfWeek(interval, dayOfWeek, timeZone).Should().BeEquivalentTo(expected);
    }

    public IEnumerable<Interval> OverlapsDayOfWeek(Interval interval, IsoDayOfWeek dayOfWeek, DateTimeZone timeZone)
    {
        throw new NotImplementedException();
    }
}
Jon Skeet
people
quotationmark

There are a few issues in the tests, but after changing those a little, they pass with the code below. In principle, it's a matter of:

  • Take the interval, and work out the dates that might be within it for any time zone. We can just convert it to a date interval in UTC and expand that by a couple of days in each direction. Output: a sequence of dates.
  • For each date within that sequence of dates, convert it to an interval in the target zone: the start is the start-of-day in that zone; the end is the start of the next day in that zone. (That will handle DST transitions.) Output: a sequence of intervals.
  • For each interval within that sequence of intervals, determine the intersection between that and the input interval. Output: a sequence of intervals, some of which may be null (for "no intersection")
  • The result is the non-null intervals in the sequence.

Here's code demonstrating that:

using System;
using System.Collections.Generic;
using System.Linq;
using NodaTime;

public class Program 
{
    public static void Main() 
    {
        var start = Instant.FromUtc(2018, 5, 11, 2, 0);
        var end = Instant.FromUtc(2018, 5, 11, 10, 0);
        var input = new Interval(start, end);

        DisplayDayIntervals(input, "America/New_York", IsoDayOfWeek.Friday);
        DisplayDayIntervals(input, "Europe/Copenhagen", IsoDayOfWeek.Friday);
    }

    static void DisplayDayIntervals(Interval input, string zoneId, IsoDayOfWeek dayOfWeek)
    {
        var zone = DateTimeZoneProviders.Tzdb[zoneId];
        var intervals = GetDayIntervals(input, zone, dayOfWeek);
        Console.WriteLine($"{zoneId}: [{string.Join(", ", intervals)}]");
    }

    public static IEnumerable<Interval> GetDayIntervals(
        Interval input,
        DateTimeZone zone,
        IsoDayOfWeek dayOfWeek)
    {
        // Get a range of dates that covers the input interval. This is deliberately
        // larger than it may need to be, to handle days starting at different instants
        // in different time zones. 
        LocalDate startDate = input.Start.InZone(DateTimeZone.Utc).Date.PlusDays(-2);
        LocalDate endDate = input.End.InZone(DateTimeZone.Utc).Date.PlusDays(2);        
        var dates = GetDates(startDate, endDate, dayOfWeek);

        // Convert those dates into intervals, each of which may or may not overlap
        // with our input.
        var intervals = dates.Select(date => GetIntervalForDate(date, zone));

        // Find the intersection of each date-interval with our input, and discard
        // any non-overlaps
        return intervals.Select(dateInterval => Intersect(dateInterval, input))
                        .Where(x => x != null)
                        .Select(x => x.Value);
    }

    private static IEnumerable<LocalDate> GetDates(LocalDate start, LocalDate end, IsoDayOfWeek dayOfWeek)
    {
        for (var date = start.With(DateAdjusters.NextOrSame(dayOfWeek));
             date <= end;
             date = date.With(DateAdjusters.Next(dayOfWeek)))
         {
             yield return date;
         }
    }

    private static Interval GetIntervalForDate(LocalDate date, DateTimeZone zone)
    {
        var start = date.AtStartOfDayInZone(zone).ToInstant();
        var end = date.PlusDays(1).AtStartOfDayInZone(zone).ToInstant();
        return new Interval(start, end);
    }

    private static Interval? Intersect(Interval left, Interval right)
    {
        Instant start = Instant.Max(left.Start, right.Start);
        Instant end = Instant.Min(left.End, right.End);
        return start < end ? new Interval(start, end) : (Interval?) null;
    }
}

people

See more on this question at Stackoverflow