[HN Gopher] How to check for overlapping intervals
___________________________________________________________________
How to check for overlapping intervals
Author : birdculture
Score : 77 points
Date : 2025-10-11 15:26 UTC (7 hours ago)
(HTM) web link (zayenz.se)
(TXT) w3m dump (zayenz.se)
| Galanwe wrote:
| 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 wrote:
| You should write that blog post.
| Terr_ wrote:
| Hmm. I imagine that determining _which_ intervals can be picked
| to make a continuous span from A to B continuous is similar to
| a graph traversal algorithm.
|
| However you aren't just given all the edges (pair overlaps)
| that exist in advance, which means there may be ways to have
| the graph-traversal side guide the edge-detection to minimize
| work.
| teddyh wrote:
| An older, and IMHO slightly more authoritative, source:
| <https://wiki.c2.com/?TestIfDateRangesOverlap>
|
| See also: <https://martinfowler.com/eaaDev/Range.html>
| rawling wrote:
| > older
|
| Hey, _I'm_ a source that's older than that one:
| <https://stackoverflow.com/a/13513973>
|
| Not so sure about "more authoritative", though.
| CaptainOfCoit wrote:
| 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...),
| last edited in 2002 at that point, but wouldn't surprise me
| to page was initially created in the 90s.
| srean wrote:
| 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.
| senderista wrote:
| 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 wrote:
| 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 wrote:
| That's what unit tests are for.
| senderista wrote:
| or better yet, property tests
| fjfaase wrote:
| 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 wrote:
| 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
| matu3ba wrote:
| 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 wrote:
| I'm saving this for Advent Of Code 2025.
| ch33zer wrote:
| Overlapping intervals were a question back in 2023 so yeah,
| it's useful
| Animats wrote:
| 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...
| efavdb wrote:
| >>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 wrote:
| 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.
| supportengineer wrote:
| 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 wrote:
| 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 wrote:
| 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/
___________________________________________________________________
(page generated 2025-10-11 23:01 UTC)