{"id":20,"date":"2017-07-09T04:28:25","date_gmt":"2017-07-09T04:28:25","guid":{"rendered":"http:\/\/edspace.com\/blog\/?p=20"},"modified":"2017-07-09T04:31:20","modified_gmt":"2017-07-09T04:31:20","slug":"algorithms-date-range-coalescing","status":"publish","type":"post","link":"http:\/\/edspace.com\/blog\/2017\/07\/09\/algorithms-date-range-coalescing\/","title":{"rendered":"Algorithms: Date Range Coalescing"},"content":{"rendered":"

I’ve done a lot of odd jobs in the software business over the years, including, but not limited to, automated UI testing, database management, package maintainer, network administration, system administration, SELinux\/SEAndroid policy writing, and download script writing. My favorite thing to do, though, is algorithm writing. I don’t get to do much of it, but I have fond-yet-frustrating memories of sitting on the floor of my cubical with a pad of paper furiously drawing out ideas so I can get them out of my head and put them into code.<\/p>\n

One of the early ones I did was a simple algorithm to coalesce a group of date ranges. The application for this algorithm would be for any situation where you needed to group blocks of time together, such as for a calendar scheduler. For example, if you need to put in a new appointment on the calendar of several, and you needed to see all available spots or simply find the first available time slot that all parties are available.<\/p>\n

When first approached with this problem, my colleague and I had the simple approach of just grouping everything into half hour or even fifteen minute buckets, and we would just scrape along and find a time bucket everyone had unoccupied. I didn’t like that idea, as it meant that we would need to store discrete blocks of time in the database somehow. I thought a more graceful solution would be to find a way to locate availability by analyzing times.<\/p>\n

Visually speaking, this is an easy problem to solve if all your appointments are laid out next to each other like this:<\/p>\n

\"Crappy
Everyone has free time from 10-11.<\/figcaption><\/figure>\n

Sure, we can see that everyone has an open slot from 10 to 11. But usually, we have our data presented to the application like so:<\/p>\n

{Chris: [ [9:00, 10:00], [12:00, 13:00] ],\r\nSteve: [ [11:00, 12:00] ],\r\nJen: [ [11:00, 12:00] ],\r\nAnne: [ [9:00, 9:30], [11:30, 12:30] ]}<\/pre>\n
This is just a small example; if you have a much larger dataset, you can imagine this would be not as trivial to do. You have to approach this from a programmatic standpoint.<\/p>\n
Attack Strategy<\/h4>\n
The general plan of attack is to try to group overlapping blocks of time into superblocks. You’ll notice that the open times sit in between the end of the last superblock and the beginning of the next superblock.<\/p>\n
\"\"<\/p>\n
So how do we find the superblocks? We can borrow the simple approach from a basic parenthesis matching algorithm, which is:<\/p>\n
    \n
  1. Start with i=0<\/em><\/li>\n
  2. Traverse your string with the following rules:
    \nif the character is an opening parenthesis, then i = i+1;<\/em>
    \nif the character is a closing parenthesis, then i=i-1;<\/em><\/li>\n
  3. Once i==0<\/em>, then the parentheses are balanced<\/li>\n<\/ol>\n
    When I first heard this algorithm, I thought it was so obvious that it wasn’t worth even mentioning. Then, I found myself doing it regularly, and I realize I probably wouldn’t have come up with it on my own.<\/p>\n
    Anyhow, we can treat our date tuples like opening and closing parentheses, and when we reach zero, then we know that we’ve concluded a superblock.<\/p>\n
    Algorithm<\/h4>\n
    The first thing we need to do is to make sure our data structures are all in place. The data type you use will largely depend on the language you are using, but anything that is sortable will do. You can use\u00a0datetime<\/em> objects or UNIX epoch seconds as integers. For the sake of simplicity, we will use simple integers here with Python.<\/p>\n
    dates = [(1,4),(2,8),(12,16),(16,21)]<\/pre>\n
     <\/p>\n
    Now remember, we don’t care who these values are associated with or how they’re currently sorted; you can pull them all from your database as one big query and dump it into your local variable.<\/p>\n
    First, we need to convert these into a flat array of date values with some sort of distinguisher between an opening or closing. There are many ways to do this, such as using a list of objects that derive from a base class as a StartingDate<\/em> or EndingDate<\/em>, or an object with a Value<\/em> and a Type<\/em>, but I will choose to simply make it a tuple, with the first value being the date value, and the second being a 1 (starting) or -1 (ending). Then, we will sort this list.<\/p>\n
    parsed_dates = []\r\nfor date in dates:\r\n    parsed_dates.extend([(date[0], 1),(date[1], -1)])\r\nparsed_dates.sort(key = lambda d: d[0])<\/pre>\n
    Next, we iterate through our new parsed_dates<\/em> structure and build our coalesced superblock list. The general rules we apply as such — for each date value:<\/p>\n