Working with Intervals

Over the last couple of months my team at Flytrex had occasion to use intervals more than once, and in both cases the team asked me, “What’s the right way to solve this?”. Since this is a common problem, I thought I’d write a short post about it.

Most interval problems seem deceptively simple, while they require more work than expected. Also, programmers aren’t always aware they are working with intervals.

Here are the two problems:

• Given the current time and a list of opening hours for a business, determine if the business is open or closed, and if it’s open – say when it will close, and if it’s closed say when it’s open. For Flytrex this is further complicated because we need to find the intersection between a restaurant’s opening hours and the opening hours of the delivery center.
• Produce a shift report for a delivery center – show the list of opening shifts (period when the center was active) – and the total flight duration for each shift (by summarizing the flight time for each delivery for each shift.)

First let’s define intervals – an interval is represented by a pair of numbers (a, b) such that it includes all the numbers between a and b. An interval may be closed or open on either side, e.g.x <= b for a closed interval or x < b for an open one. In addition, it’s sometimes useful to allow a to be -inf and b +inf.

Now we can define operations on intervals – union, intersection and inversion, such that the input and output of each operation is a set of intervals.

As an anecdote – one of the questions I ask candidates in Flytrex includes an intersection between intervals – check if two intervals intersect. The naive solution is “let’s map all the cases”, which is hard. The easier solution is to understand the cases when they don’t intersect (b2 < a1 OR b1 < a2), and then NOT the result.

The first trick for solving interval problems is to realize they are interval problems. One of our developers asked some friends about his particular problem – and most suggestions revolved around lookup tables and binary search, which might work but are complex and not a direct solution.

The right way to solve an interval problem is using an interval tree. The second trick is of course not to develop one yourself but instead to find a library. For the developer faced with the interval problem – it transformed a very complex problem to 5 lines of easy code. My hope with this post – the next time you are faced with an interval problem – you’ll know how to solve it the right way – which is also the easy way. Let me know if you do!