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.
... continue reading