Skip to main content

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.

Popular posts from this blog

Full-Text Search with PDF in Microsoft SQL Server

Last week I get interesting task to develop. The task was to search input text in PDF file stored in database as FileStream. The task implementation took me some time so I decided to share it with other developers. Here we are going to use SQL Server 2008 R2 (x64 Developers Edition), external driver from Adobe, Full-Text Search technology and FileStream technology.Because this sems a little bit comlicated let`s make this topic clear and do it step by step. 1) Enable FileStream - this part is pretty easy, just check wheter You already have enabled filestream on Your SQL Server instance - if no simply enable it as in the picture below. Picture 1. Enable filestream in SQL Server instance. 2) Create SQL table to store files  - mainly ther will be PDF file stored but some others is also be allright. Out table DocumentFile will be created in dbo schema and contain one column primary key with default value as sequential GUID. Important this is out table contains FileStream

Playing with a .NET types definition

In the last few days I spent some time trying to unify structure of one of the project I`m currently working on. Most of the changes were about changing variable types because it`s were not used right way. That is why in this post I want to share my observations and practices with you. First of all we need to understand what ' variable definition ' is and how it`s different from ' variable initialization '. This part should be pretty straightforward:   variable definition  consist of data type and variable name only <data_type> <variable_name> ; for example int i ; . It`s important to understand how variable definition affects your code because it behaves differently depends weather you work with value or reference types. In the case of value types after defining variable it always has default value and it`s never null value. However after defined reference type variable without initializing it has null value by default. variable initialization  is

Persisting Enum in database with Entity Framework

Problem statement We all want to write clean code and follow best coding practices. This all engineers 'North Star' goal which in many cases can not be easily achievable because of many potential difficulties with converting our ideas/good practices into working solutions.  One of an example I recently came across was about using ASP.NET Core and Entity Framework 5 to store Enum values in a relational database (like Azure SQL). Why is this a problem you might ask... and my answer here is that you want to work with Enum types in your code but persist an integer in your databases. You can think about in that way. Why we use data types at all when everything could be just a string which is getting converted into a desirable type when needed. This 'all-string' approach is of course a huge anti-pattern and a bad practice for many reasons with few being: degraded performance, increased storage space, increased code duplication.  Pre-requirements 1. Status enum type definition