How to check for overlapping intervals

Overlap in multiple dimensions is simply the AND of overlap in each dimension.

The 3D case comes up in collision detection.

For collision detection in games, the objects are usually kept in a sorted order, with separate lists for X, Y and Z. Amusingly, a bubble sort is useful, because, as objects move, they tend to move locally, so a bubble sort quickly restores the order. The sorting algorithm should terminate quickly when there are few or no changes. First seen in I-Collide, 1995. When objects are moving slowly, speed is slightly worse than O(N), but degrades if there's too much motion.

2D sorting speeds things up. If you sort the intervals by start X, start Y, you can process the intervals sequentially. Here's something of mine which does that.[1] A MySQL database does the sort, then feeds the data to this algorithm. Overlaps are detected, sets of overlapping objects are merged, and the sets of overlapping 2D rectangles are emitted. Sort is O(N log N) as usual, and overlap detection is O(N).

[1] https://github.com/John-Nagle/maptools/blob/main/rust/src/ge...

This seemingly no-brainer of a task becomes more intellectually interesting than what you may think on first contact (pun intended).

More so when you have to distinguish between the different types of overlap and non overlap and carry through the reasoning over a chain of overlap/no-overlap relations. I sure underestimated it.

The one dimensional case is covered(there you go again) by Allen algebra. The more richer notion is that of topological relations. I will find the Wikipedia pages and post.

https://en.wikipedia.org/wiki/Allen%27s_interval_algebra

https://en.wikipedia.org/wiki/Region_connection_calculus

https://en.wikipedia.org/wiki/Spatial_relation

https://en.wikipedia.org/w/index.php?title=DE-9IM

Interval trees, range trees help if you have a large static set of interval like objects against which you have to relate a query object.

My work involves a lot of time series analysis, as such I'm often dealing with intervals.

While the overlap algorithm (or rather "condition") is cute, there a lot more "cool" stuff to do with intervals, which I would have liked to see in there.

- Checking whether multiple intervals overlap

- Checking whether multiple intervals are contiguous

- Merging contiguous intervals

- Etc..

From experience, something is also crucial when working with intervals: trivially knowing which boundaries are closed and which are opened. I found that defining a strict vocabulary helps a lot here. e.g. "last" is "inclusive", while "end" is exclusive.

[closed; opened[ intervals are also the best when dealing with time intervals (if that makes sense in your use case), because you can trivially join them.

An older, and IMHO slightly more authoritative, source: <https://wiki.c2.com/?TestIfDateRangesOverlap>

See also: <https://martinfowler.com/eaaDev/Range.html>

R-Trees are a good data structure to use in this case, enabling you to query a collection of intervals for overlap with another in O(log(n)) time.

Wikipedia: https://en.wikipedia.org/wiki/R-tree

I find it interesting that I don't have a good intuition for the simple condition; instead I have to follow something like the process in the article whenever I want to re-derive that condition.

"Invert, always invert" -- Carl Jacobi

I've written code like this to work with overlapping genes. While most genes exist in a genome with spacers between them and their neighboring genes, sometimes you get pairs of genes which overlap, and there seems to be some interesting biology that happens as a consequence.

Here's a package for Python that presumably uses some sort index data structure to be efficient: https://pyranges.readthedocs.io/en/latest/

Nice introduction.

1. Please always make closed and open interval explicit on all code examples. "Detecting overlap" is ambiguous and open intervals have no given solution in the article, if I'm not mistaken. 2. How do you define the empty interval on floating point numbers? How do you define an open interval on floating point numbers? Number representation, input range etc can be very important.

Disclosure: Did some stupidly crazy time series eval for OCPP1.6 and OCPP2.01 charging profiles.

Even with the visualization, I found the minimal solution hard to visualize. I came up with this instead:

Suppose you start with two separated intervals. The left one starts sliding rightward. At what point do they contact? That's easy, it's just when (end1 > start2).

As it continues sliding, at what point do they lose contact? Again, easy: it's where (start1 >= end2).

So the solution is the first condition and the negation of the second, i.e.: (end1 > start2) && (start1 < end2)

I had to do this with 1-day granularity in SQL so we created a Day dimension table and just did a join to detect the overlapping days.

Now write some code to manage collectons of intervals and operations, such as finding if a value is included in a collection of intervals and operations for merging two collections of intervals. What is the best data structure to be used? Explain why?

Spacetime overlaps can depend on the velocity of the observer if far enough apart. Not sure if it's worth figuring that into the code.

I'm saving this for Advent Of Code 2025.