3 ms·

How to check for overlapping intervals

97 points by birdculture 1y ago

Galanwe 1y ago
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.
- ambicapter 1y ago
  You should write that blog post.
- Terr_ 1y ago
  Hmm. I imagine that determining which intervals can be picked to make a continuous span is really a graph-traversal algorithm. However you aren't just given all the existing edges (pair overlaps) in advance, maybe there's a way to have the graph-exploration side guide the edge-detection to minimize work.
teddyh 1y ago
An older, and IMHO slightly more authoritative, source: <https://wiki.c2.com/?TestIfDateRangesOverlap https://wiki.c2.com/?TestIfDateRangesOverlap> See also: <https://martinfowler.com/eaaDev/Range.html https://martinfowler.com/eaaDev/Range.html>
- rawling 1y ago
  > older Hey, _I'm_ a source that's older than that one: <https://stackoverflow.com/a/13513973 https://stackoverflow.com/a/13513973> Not so sure about "more authoritative", though.
  - CaptainOfCoit 1y ago
    Bold to claim something you've authored on Stack Overflow is older than C2, the og wiki. The earliest version I could find on IA is from 2003 (https://web.archive.org/web/20030606033520/http://c2.com/cgi/wiki?TestIfDateRangesOverlap https://web.archive.org/web/20030606033520/http://c2.com/cgi...), last edited in 2002 at that point, but wouldn't surprise me to page was initially created in the 90s.
    - rawling 1y ago
      Hah, damn. I just saw the date at the bottom and ignored the bit that said "last edit".
      - CaptainOfCoit 1y ago
        No worries :) Do go through that entire Wiki if you haven't before, somewhat of an gold mine of good (but old) programming tips and tricks. Some information is a bit dated at this point though, but I still think it's one of the best resources out there.
srean 1y ago
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/Allen%27s_interval_algebra https://en.wikipedia.org/wiki/Region_connection_calculus https://en.wikipedia.org/wiki/Region_connection_calculus https://en.wikipedia.org/wiki/Spatial_relation https://en.wikipedia.org/wiki/Spatial_relation https://en.wikipedia.org/w/index.php?title=DE-9IM 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.
senderista 1y ago
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.
- tirutiru 1y ago
  I wonder how many completely u related applications have that interval check logic coded up somewhere. I'm pretty sure I wrote one for my work codebase. Would I bet my life that the < and <=s are correct? Nope.
  - Animats 1y ago
    That's what unit tests are for.
    - senderista 1y ago
      or better yet, property tests
fjfaase 1y ago
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?
joshlk 1y ago
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 https://en.wikipedia.org/wiki/R-tree
matu3ba 1y ago
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.
OptionOfT 1y ago
I'm saving this for Advent Of Code 2025.
- sour-taste 1y ago
  Overlapping intervals were a question back in 2023 so yeah, it's useful
Animats 1y ago
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/generator/vizgroup.rs https://github.com/John-Nagle/maptools/blob/main/rust/src/ge...
- efavdb 1y ago
  >>Overlap in multiple dimensions is simply the AND of overlap in each dimension. Presumably just for boxes aligned with the axes (or some other condition?)? EG two lines can have x’s in common and y’s but not overlap if they are sloped at some angle.
  - Animats 1y ago
    Right, axis-aligned bounding boxes. Most collision detection systems use axis-aligned bounding boxes as a filter. Then more detailed algorithms are used on possibly-colliding objects.
    - efavdb 1y ago
      Interesting, thanks!
- deleted 1y ago
  [deleted]
- 1y ago
supportengineer 1y ago
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.
SyzygyRhythm 1y ago
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)
dekhn 1y ago
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/ https://pyranges.readthedocs.io/en/latest/
tim333 1y ago
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.
penguin_booze 1y ago
"Invert, always invert" -- Carl Jacobi

97 points by birdculture 1y ago

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.

ambicapter 1y ago
You should write that blog post.
Terr_ 1y ago
Hmm. I imagine that determining which intervals can be picked to make a continuous span is really a graph-traversal algorithm. However you aren't just given all the existing edges (pair overlaps) in advance, maybe there's a way to have the graph-exploration side guide the edge-detection to minimize work.

teddyh 1y ago

An older, and IMHO slightly more authoritative, source: <https://wiki.c2.com/?TestIfDateRangesOverlap https://wiki.c2.com/?TestIfDateRangesOverlap> See also: <https://martinfowler.com/eaaDev/Range.html https://martinfowler.com/eaaDev/Range.html>

rawling 1y ago
> older Hey, _I'm_ a source that's older than that one: <https://stackoverflow.com/a/13513973 https://stackoverflow.com/a/13513973> Not so sure about "more authoritative", though.
- CaptainOfCoit 1y ago
  Bold to claim something you've authored on Stack Overflow is older than C2, the og wiki. The earliest version I could find on IA is from 2003 (https://web.archive.org/web/20030606033520/http://c2.com/cgi/wiki?TestIfDateRangesOverlap https://web.archive.org/web/20030606033520/http://c2.com/cgi...), last edited in 2002 at that point, but wouldn't surprise me to page was initially created in the 90s.
  - rawling 1y ago
    Hah, damn. I just saw the date at the bottom and ignored the bit that said "last edit".
    - CaptainOfCoit 1y ago
      No worries :) Do go through that entire Wiki if you haven't before, somewhat of an gold mine of good (but old) programming tips and tricks. Some information is a bit dated at this point though, but I still think it's one of the best resources out there.

srean 1y ago

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/Allen%27s_interval_algebra https://en.wikipedia.org/wiki/Region_connection_calculus https://en.wikipedia.org/wiki/Region_connection_calculus https://en.wikipedia.org/wiki/Spatial_relation https://en.wikipedia.org/wiki/Spatial_relation https://en.wikipedia.org/w/index.php?title=DE-9IM 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.

senderista 1y ago

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.

tirutiru 1y ago
I wonder how many completely u related applications have that interval check logic coded up somewhere. I'm pretty sure I wrote one for my work codebase. Would I bet my life that the < and <=s are correct? Nope.
- Animats 1y ago
  That's what unit tests are for.
  - senderista 1y ago
    or better yet, property tests

fjfaase 1y ago

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?

joshlk 1y ago

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 https://en.wikipedia.org/wiki/R-tree

matu3ba 1y ago

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.

OptionOfT 1y ago

I'm saving this for Advent Of Code 2025.

sour-taste 1y ago
Overlapping intervals were a question back in 2023 so yeah, it's useful

Animats 1y ago

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/generator/vizgroup.rs https://github.com/John-Nagle/maptools/blob/main/rust/src/ge...

efavdb 1y ago
>>Overlap in multiple dimensions is simply the AND of overlap in each dimension. Presumably just for boxes aligned with the axes (or some other condition?)? EG two lines can have x’s in common and y’s but not overlap if they are sloped at some angle.
- Animats 1y ago
  Right, axis-aligned bounding boxes. Most collision detection systems use axis-aligned bounding boxes as a filter. Then more detailed algorithms are used on possibly-colliding objects.
  - efavdb 1y ago
    Interesting, thanks!
deleted 1y ago
[deleted]
1y ago

supportengineer 1y ago

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.

SyzygyRhythm 1y ago

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)

dekhn 1y ago

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/ https://pyranges.readthedocs.io/en/latest/

tim333 1y ago

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.

penguin_booze 1y ago

"Invert, always invert" -- Carl Jacobi