How to Check for Overlapping Intervals

Summary

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) Numeric ranges: [1, 10) (the digit 1, 2, 3, …, 9) Date ranges: [2025-01-01, 2025-12-31] (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 from start to end (exclusive)""" 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 def overlaps(self, other: Interval) -> bool: """ Return true iff the two intervals overlap. """ 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 distin...