Finding gaps in time

Let assume that we want to create a simple scheduler which allow user to plan meeting as long as he want with 1 minute precision. There is multiple ways to make such implementation but in this post I want to present an approach I used recently.

In my implementation I`ve created separated type which represents any time period. I called it Range and it`s consists of three properties (one is read-only). Main idea behind creating this time is encapsulate state and end date of used defined time period.

    /// <summary>
    /// Represents range in time.
    /// </summary>
    public class Range
    {
        /// <summary>
        /// Gets or sets represents range start time.
        /// </summary>
        public DateTime StartTime { get; set; }

        /// <summary>
        /// Gets or sets represents range end time.
        /// </summary>
        public DateTime EndTime { get; set; }

        /// <summary>
        /// Gets range period.
        /// </summary>
        public TimeSpan Duration
        {
            get
            {
                return this.EndTime.Subtract(this.StartTime);
            }
        }
    }

I`ve also created a Scheduler class. This class consists of only a few function as follow:

• AddRange - add new date range  to the collection on booked ranges if new range don`t overlapping with any existing range.
• GetAllBookedDates - returns all booked date ranges as IReadOnlyCollection<Range> collection
• Overlaps (with two overloads) - bool value which determines whether two time ranges are overlapping each other - also four DateTime objects can be used.
• GetFreeTime - searching for not booked ranges of time for given time boundary.

Picture 1. Program dependencies.

Not it`s  time for implementation part. Before creating core implementation of the gaps finding algorithm we need to create a simple static (can be also non-static) which allow to detect overlaps in a given period of time. An overload method of this function takes two parameters of Range type.

Picture 2. Idea of overlapping a two time ranges.

public static bool Overlaps(DateTime firstStart, DateTime firstEnd, DateTime secondStart, DateTime secondEnd)
        {
            return (secondStart >= firstStart && secondStart < firstEnd) ||
                (secondEnd <= firstEnd && secondEnd > firstStart) ||
                (secondStart <= firstStart && secondEnd >= firstEnd) ||
                (firstStart <= secondStart && firstEnd >= secondEnd);
        }

Now its time for the implementation of the most important function in whole program - finding free gaps in time. Assumption in this algorithm is precision up to 1 minute so it`s means that seconds and milliseconds are not taken under consideration while processing. After validating validity of the input, edge DateTime parameters a new collection of integer is created. Collection of integers is noting else but number of minutes inside edge DateTime range. Inside the for loop i variable is incremented and value of i represents number of minutes since lower boundary.

        /// <summary>
        /// Finds gaps in given time.
        /// </summary>
        /// <param name="lowerBoundDate">Minimum date to get range for.</param>
        /// <param name="upperBoundDate">Maximum date to get range for.</param>
        /// <returns>Collection of free ranges.</returns>
        public IEnumerable<Range> GetFreeTime(DateTime lowerBoundDate, DateTime upperBoundDate)
        {
            if (this.BookedDates == null)
            {
                throw new InvalidOperationException("BookedDates can not be null");
            }

            if (lowerBoundDate >= upperBoundDate)
            {
                throw new InvalidOperationException("lowerBoundDate can not be greater or equals to upperBoundDate.");
            }

            if (!this.BookedDates.Any())
            {
                return new List<Range>() { new Range() { StartTime = lowerBoundDate, EndTime = upperBoundDate } };
            }

            var resultList = new List<Range>();
            var delta = upperBoundDate - lowerBoundDate;
            var totalRangeMinutes = Enumerable.Range(0, (int)delta.TotalMinutes).ToArray();
            var currentDate = lowerBoundDate;
            var currentRange = new Range();
            Range freeRange = null;

            for (var i = 0; i < totalRangeMinutes.Count(); i++)
            {
                currentRange = new Range() { StartTime = currentDate, EndTime = currentDate.AddMinutes(1) };

                var overlappingRange = this.BookedDates.FirstOrDefault(c => this.Overlaps(currentRange.StartTime, currentRange.EndTime, c.StartTime, c.EndTime));

                if (overlappingRange != null)
                {
                    // Increment i to the end of current overlapping range.
                    i = (int)overlappingRange.EndTime.Subtract(lowerBoundDate).TotalMinutes + 1;

                    freeRange.EndTime = lowerBoundDate.AddMinutes((int)overlappingRange.StartTime.Subtract(lowerBoundDate).TotalMinutes);
                    resultList.Add(freeRange);
                    freeRange = null;
                }
                else
                {
                    if (freeRange == null)
                    {
                        freeRange = new Range() { StartTime = currentDate };
                    }
                }

                currentDate = lowerBoundDate.AddMinutes(i);
            }
         
             // Handle the case where we have free  time until reach upper boundary.
            if (freeRange != null && freeRange.StartTime > lowerBoundDate)
            {

                if (freeRange.EndTime < freeRange.StartTime)
                {
                    freeRange.EndTime = upperBoundDate;
                }

                resultList.Add(freeRange);
            }

            return resultList;
        }

After these functions have been created it`s time for test it.

static void Main(string[] args)
        {
            var scheduler = new Scheduler();

            scheduler.AddRange(new Range() { StartTime = DateTime.UtcNow.AddDays(1), EndTime = DateTime.UtcNow.AddDays(1).AddHours(1) });
            scheduler.AddRange(new Range() { StartTime = DateTime.UtcNow.AddDays(1).AddHours(4), EndTime = DateTime.UtcNow.AddDays(1).AddHours(5) });

            Console.WriteLine("Booked dates.");
            var usedDates = scheduler.GetAllBookedDates();
            PrintDates(usedDates);

            Console.WriteLine("Free dates.");
            var result = scheduler.GetFreeTime(DateTime.Today.AddDays(1), DateTime.Today.AddDays(2));
            PrintDates(result);
        }

        /// <summary>
        /// Prints result to the console.
        /// </summary>
        /// <param name="ranges">Ranges to</param>
        private static void PrintDates(IEnumerable<Range> ranges)
        {
            foreach (var range in ranges)
            {
                Console.WriteLine("Start date: {0} - end date: {1}.", range.StartTime, range.EndTime);
            }
        }

Whole source code of the project is available here.

Thank you.