How to Check for Overlapping Intervals

Working with intervals is a common task in programming, whether you’re dealing with time ranges, scheduling problems, or geometric computations. A key insight when working with intervals is that checking for the absence of an overlap is often much simpler than checking for all the ways an overlap can occur. This post will first cover how to represent intervals in code, then dive into the logic for detecting overlaps. An interval represents a range between two points, and could be in a continuous or discrete domain. A common way to write an interval is a pair of values [start, end] where start ≤ end . This would be a so-called closed interval, where the end-value is included in the interval. An alternative is [start, end) , which denotes a half-open interval where the end value is not included in the interval.1 Half-open intervals are very common in programming languages. Some examples of intervals are Time intervals: [9:00, 17:00] (a work day) (a work day) Numeric ranges: [1, 10) (the digit 1, 2, 3, …, 9) (the digit 1, 2, 3, …, 9) Date ranges: [2025-01-01, 2025-12-31] (all the days in the year 2025) (all the days in the year 2025) Temperature range: [20°C, 25°C] … We will use Python as an example language, and will use plain integers as the underlying type. All the examples will use open intervals, as that is very common. interval.py @dataclass class Interval : """Interval from start to end (exclusive)""" start: int end: int # Useful methods ... For the purposes of this post, we will only consider integer valued intervals for simplicity. In addition we require that intervals are non-empty. In many real cases, real valued intervals approximated by floating points are needed as is the handling of empty intervals. One of the most common questions when working with intervals is: “Do these two intervals overlap?” Lets implement a method for this @dataclass class Interval : ... def overlaps ( self , other : Interval) -> bool : """ Return true iff the two intervals overlap. """ # How to implement? Whenever one needs to make a Boolean condition, the easiest way is often to consider all the cases. So, let’s consider all the ways that two intervals may overlap. There are four distinct cases. 1 3 5 7 9 self other Case 1: self starts first, other overlaps end of self 1 3 5 7 9 self other Case 2: other starts first, self overlaps end of other 1 3 5 7 9 self other Case 3: self completely contains other 1 3 5 7 9 self other Case 4: other completely contains self In all these cases, we can see that the intervals share at least one point in common. The challenge is to write a condition that captures all four cases correctly. Let’s translate it into code straight from the case analysis. @dataclass class Interval : ... def overlaps ( self , other : Interval) -> bool : """ Return true iff the two intervals overlap. """ return \ # Case 1 self .start <= other.start < self .end or # Case 2 self .start < other.end <= self .end or # Case 3 self .start < other.end <= other.end < self .end or # Case 4 other.start <= self .start <= self .end < other.end This is a straightforward translation of the cases, where the most tricky thing is to make sure that the handling of the half-open property is correct. One thing to note though, is that by checking the endpoints of the blue other interval in Case 1 and 2, then we have also covered Case 3. This means that due to short circuiting, we will never trigger Case 3. In addition Case 4 is overly specific. We only need to care about checking if the start-point of the green self interval is in the blue other interval. Taking these observations into account, we can simplify the above condition to the following cases. @dataclass class Interval : ... def overlaps ( self , other : Interval) -> bool : """ Return true iff the two intervals overlap. """ return \ # Case 1 self .start <= other.start < self .end or # Case 2 self .start < other.end <= self .end or # Case 4 (simplified) other.start <= self .start < other.end With a case-analysis and some careful considerations, we have a nice expression that captures overlapping intervals. But checking overlap feels like something that should be obvious, and this condition is not that obvious. Checking for overlap of two intervals also feels like it shouldn’t reduce down to three cases. From that argument, we can intuit that it should be possible to simplify this even more. Can we make a simpler condition, that is also easy to find? The core insight is that sometimes it is much easier to check for the negation of a property than the original property. For overlap, the negation is checking if two intervals are not overlapping. Let’s look at the cases we have now instead. 1 3 5 7 9 self other Case 1: self is before other 1 3 5 7 9 self other Case 2: other is before self There are only two ways the two intervals are not overlapping, and this is much easier to translate into code. @dataclass class Interval : ... def overlaps ( self , other : Interval) -> bool : """ Return true iff the two intervals overlap. """ return not ( # Case 1 self .end <= other.start or # Case 2 other.end <= self .start ) Using De Morgan’s law ( ¬ ( A ∨ B ) ⊢ ¬ A ∧ ¬ B ) \left( \lnot (A \lor B) \large\vdash \lnot A \land \lnot B \right) (¬(A∨B)⊢¬A∧¬B) it is possible to push the negation in. In addition, negated comparisons can be flipped ( ¬ x ≤ y ⊢ y < x ) \left(\lnot x \leq y \large\vdash y < x\right) (¬x≤y⊢y bool : """ Return true iff the two intervals overlap. """ return ( other.start < self .end and self .start < other.end ) This is finally a nice and simple expression that checks just two properties. By changing our viewpoint from checking for an overlap to checking against one, we deduced the correct expression much more easily. The new condition works, and we could derive it from a case analysis and using Boolean simplification. But there is also a meaning to the expression that we can interpret geometrically. 1 3 5 7 9 self other Case 1: start of other is before end of self 1 3 5 7 9 self other Case 2: start of self is before end of other The first case checks that it is not the case that other starts after self ends. The second case checks that it is not the case that self starts after other ends. These two conditions together gives us the result that there is some part that is overlapping. It is of course possible to figure out this condition directly, but making this intuitive leap is in my view harder than following the case analysis from the negative case.2 An interval is a one-dimensional property. A very natural extension is to instead consider two-dimensional properties. Representing a box is very similar to an interval, here we go from top and left (inclusive) to bottom and right (exclusive). box.py @dataclass class Box : """Box from (left, top) to (right, bottom) (exclusive)""" left: int right: int bottom: int top: int # Useful methods ... Checking for overlap is equally important for boxes as it is for intervals. Let’s start by making a full case analysis of all the variants for how two boxes can overlap. 1 3 5 7 9 1 3 5 7 9 self other Case 1: other left+below, ends inside 1 3 5 7 9 1 3 5 7 9 self other Case 2: other left, ends inside; contained vertically 1 3 5 7 9 1 3 5 7 9 self other Case 3: other left+above, ends inside 1 3 5 7 9 1 3 5 7 9 self other Case 4: other left, ends inside; contains vertically 1 3 5 7 9 1 3 5 7 9 self other Case 5: other contained horizontally; starts below, ends inside 1 3 5 7 9 1 3 5 7 9 self other Case 6: other fully contained in self 1 3 5 7 9 1 3 5 7 9 self other Case 7: other contained horizontally; starts inside, ends above 1 3 5 7 9 1 3 5 7 9 self other Case 8: other contains self horizontally; overlaps vertically 1 3 5 7 9 1 3 5 7 9 self other Case 9: other right+below, starts inside 1 3 5 7 9 1 3 5 7 9 self other Case 10: other right, starts inside; contained vertically 1 3 5 7 9 1 3 5 7 9 self other Case 11: other right+above, starts inside 1 3 5 7 9 1 3 5 7 9 self other Case 12: other right, starts inside; contains vertically 1 3 5 7 9 1 3 5 7 9 self other Case 13: other contains horizontally; starts below, ends inside 1 3 5 7 9 1 3 5 7 9 self other Case 14: other contains horizontally; contained vertically 1 3 5 7 9 1 3 5 7 9 self other Case 15: other contains horizontally; starts inside, ends above 1 3 5 7 9 1 3 5 7 9 self other Case 16: other completely contains self This does not inspire confidence in getting understandable code, let’s not even attempt it. Using the same idea as for intervals, let’s look at the cases where two boxes do not overlap. 1 3 5 7 9 1 3 5 7 9 self other Case 1: other is to the left of self 1 3 5 7 9 1 3 5 7 9 self other Case 2: other is to the right of self 1 3 5 7 9 1 3 5 7 9 self other Case 3: other is above self 1 3 5 7 9 1 3 5 7 9 self other Case 4: other is below self This is quite easy, the other box can be to the left, right, above, or below. If it is to the left, it does not matter how much (or at all) the box overlaps in the vertical direction. Translating this into straightforward code as before. @dataclass class Box : ... def overlaps ( self , other : Box) -> bool : """ Return true iff the two boxes overlap. """ return not ( # Case 1 self .right <= other.left or # Case 2 other.right <= self .left or # Case 3 self .top <= other.bottom or # Case 4 other.bottom <= self .top ) Using the same analysis as before, we can use De Morgan’s laws to change the implementation to not start with a not.3 @dataclass class Box : ... def overlaps ( self , other : Box) -> bool : """ Return true iff the two boxes overlap. """ return ( other.left < self .right and self .left < other.right and other.bottom < self .top and self .bottom < other.top ) This new expression can be interpreted as a two dimensional variant of the interval overlap check. Two boxes overlap if there is overlap in both the horizontal and the vertical direction. Figuring out the best way to express a property can be tricky. For intervals, while one can sit down and think thoroughly to find the best way to express the overlaps property, it is not easy. Using case analysis is the straight-forward way to create these but it can easily lead to an overly complicated and error-prone expression. This is especially clear for the box case, where there are 16 different cases to handle. Using negation as a trick to simplify the case analysis works really well here. Naturally, it doesn’t always work out this well, but when it does it is a technique that is worth keeping in mind.