How to find gaps between multiple, variable DateRanges in C#

Question

I'm doing an appointment finder, where you can input multiple users' appoiments and it should find empty gaps in a list with multiple and variable DateRanges. The methods I wrote do unfortunately not work. How could I do this without a large library like TimePeriodLibrary.

List<DateRange> appointments = new List<DateRange>();

appointments.Add(new DateRange(new DateTime(2020, 7, 6, 10, 30, 0), new DateTime(2020, 7, 6, 11, 30, 0)));

appointments.Add(new DateRange(new DateTime(2020, 7, 7, 8, 30, 0), new DateTime(2020, 7, 7, 15, 30, 0)));

appointments.Add(new DateRange(new DateTime(2020, 7, 6, 16, 30, 0), new DateTime(2020, 7, 6, 17, 0, 0)));

var gaps = FindGapsInUsersCalendars(appointments, 60);

if (gaps.Any())
{
    foreach (var gap in gaps)
    {
        Console.WriteLine($"{gap.Start} - {gap.End}");
    }
}



private static List<DateRange> FindGapsInUsersCalendars(List<DateRange> appointments, int minutes)
{
    List<DateRange> possibilities = new List<DateRange>();

    foreach (var appointment in appointments)
    {
        if (!DateRangeIncludesDateForMinutes(appointment, appointment.End, minutes)) continue;

        possibilities.Add(new DateRange(appointment.Start, appointment.Start.AddMinutes(minutes)));
    }

    return possibilities;
}

private static bool DateRangeIncludesDateForMinutes(DateRange dateRange, DateTime date, int minutes)
{
    var tempDate = date;

    for (var i = 0; i < minutes; i++)
    {
        if (!dateRange.Includes(tempDate.AddMinutes(1))) {
            return false;
        }
    }

    return true;
}

DateRange.cs class:

public class DateRange : IRange<DateTime>
    {
        public DateRange(DateTime start, DateTime end)
        {
            Start = start;
            End = end;
        }

        public DateTime Start { get; private set; }
        public DateTime End { get; private set; }

        public bool Includes(DateTime value)
        {
            return (Start <= value) && (value <= End);
        }

        public bool Includes(IRange<DateTime> range)
        {
            return (Start <= range.Start) && (range.End <= End);
        }
    }

IRange.cs interface:

public interface IRange<T>
    {
        T Start { get; }
        T End { get; }
        bool Includes(T value);
        bool Includes(IRange<T> range);
    }

Answer 1

I don't have time to create code for this, but here's a relatively simple algorithm you can try to implement in order to find gaps after each appointment:

• Order all appointments by increasing start-time.
• Iterate over the appointments, and for each one: Search for any appointment that has a start-time that is less than or equal to the current appointment's end-time.
  • If so: Does that conflicting appointment end before or at the same time as the current appointment?
    • If so, ignore it and continue looking for other conflicting appointments.
    • If not (it ends after the current appointment), you know there is no free time directly after the current appointment, so break and skip to checking the next appointment instead.
      • (Actually you could skip to the conflicting appointment, since you already know there will at least not be any break until that one ends).
  • If not: Congratulations, you've found an appointment after which there is some free time!

Tip: Visualize each appointment as a timeline while thinking about this, and look for where they overlap:

|-------------|
    |--------|
       |------------|
                |----------| 
                  |-------| 
                             <free time>  
                                         |-----------|
                                              |------------|

Answer 2

Here is my solution. It uses my own generic range-type with Max/Min rather than Start/End. But I hope it is clear enough to make sense of.

The overall approach is to merge all overlapping ranges into continuous, non-overlapping ranges, and then simply return the space between each subsequent range. I would recommend writing some more tests, there might be edge cases I have not considered.

    public bool Intersects<T>(Range<T> left, Range<T> right) where T : IComparable<T>
    {
        return !(left.Max.CompareTo(right.Min) < 0 ||
            right.Max.CompareTo(left.Min) < 0);
    }

    public Range<T> Union<T>(Range<T> left, Range<T> right) where T : IComparable<T>
    {
        var min = left.Min.CompareTo(right.Min) < 0 ? left.Min : right.Min;
        var max = left.Max.CompareTo(right.Max) > 0 ? left.Max : right.Max;
        return new Range<T>(min, max);
    }
    public List<Range<T>> Merge<T>(IEnumerable<Range<T>> ranges) where T : IComparable<T>
    {
        var orderedRanges = ranges.OrderBy(r => r.Max).ToList();
        for (int i = orderedRanges.Count-2; i >= 0; i--)
        {
            var current = orderedRanges[i + 1];
            var previous = orderedRanges[i];
            if (Intersects(current, previous))
            {
                var union = Union(current, previous);
                orderedRanges[i] = union;
                orderedRanges.RemoveAt(i+1);
            }
        }
        return orderedRanges;
    }

    public IEnumerable<Range<T>> Gaps<T>(IEnumerable<Range<T>> ranges) where T : IComparable<T>
    {
        var merged = Merge(ranges).OrderBy(r => r.Max).ToList();

        for (int i = 0; i < merged.Count-1; i++)
        {
            var current = merged[i];
            var next = merged[i + 1];
            yield return new Range<T>(current.Max, next.Min);
        }
    }

Test case:

    [Test]
    public void TestGaps()
    {
        var sut = new[]
        {
            new Range<int>(0, 4),
            new Range<int>(1, 2),
            new Range<int>(3, 6),
            new Range<int>(5, 10),
            // Gap
            new Range<int>(12, 15),
            new Range<int>(13, 14),
            // Gap
            new Range<int>(20, 25),
        };
        var results = Gaps(sut);
        var expected = new[]
        {
            new Range<int>(10, 12),
            new Range<int>(15, 20),
        };

        CollectionAssert.AreEqual(expected, results);
    }

Edit: The significant difference in my range type is the use of generic constraint to ensure the values can be compared. It is also a struct to avoid allocations. The signature I use is

public readonly struct Range<T> : where T : IComparable<T> 
{
    public T Min { get; }
    public T Max { get; }
    public Range(T min, T max) => (Min, Max) = (min, max);
    // Bunch of methods
}

You could also use extension methods to gain a similar benefit, like

    public static bool Intersects<T>(this IRange<T> self, IRange<T> other) where T : IComparable<T>

or

    public static bool Intersects<T>(this IRange<T> self, IRange<T> other, IComparer<T> comparer)