How to find range overlap in python?

The answers above seem mostly overly complex. This one liner works perfectly in Python3, takes ranges as inputs and output. It also handles illegal ranges. To get the values just iterate over the result if not None.

# return overlap range for two range objects or None if no ovelap
# does not handle step!=1
def range_intersect(r1, r2):
    return range(max(r1.start,r2.start), min(r1.stop,r2.stop)) or None

If you looking for the overlap between two real-valued bounded intervals, then this is quite nice:

def overlap(start1, end1, start2, end2):
    """how much does the range (start1, end1) overlap with (start2, end2)"""
    return max(max((end2-start1), 0) - max((end2-end1), 0) - max((start2-start1), 0), 0)

I couldn't find this online anywhere so I came up with this and I'm posting here.

This is the answer for the simple range with step=1 case (99% of the time), which can be 2500x faster as shown in the benchmark when comparing long ranges using sets (when you are just interested in knowing if there is overlap):

x = range(1,10) 
y = range(8,20)

def range_overlapping(x, y):
    if x.start == x.stop or y.start == y.stop:
        return False
    return x.start <= y.stop and y.start <= x.stop

>>> range_overlapping(x, y)
True

To find the overlapping values:

def overlap(x, y):
    if not range_overlapping(x, y):
        return set()
    return set(range(max(x.start, y.start), min(x.stop, y.stop)+1))

Visual help:

|  |           |    |
  |  |       |    |

Benchmark:

x = range(1,10)
y = range(8,20)

In [151]: %timeit set(x).intersection(y)
2.74 µs ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [152]: %timeit range_overlapping(x, y)
1.4 µs ± 2.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Conclusion: even for small ranges, it is twice as fast.

x = range(1,10000)
y = range(50000, 500000)

In [155]: %timeit set(x).intersection(y)
43.1 ms ± 158 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [156]: %timeit range_overlapping(x, y)
1.75 µs ± 88.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Conclusion: you want to use the range_overlapping function in this case as it is 2500x faster (my personal record in speedup)

This solution generates integers that are in the intersection of an arbitrary number of range objects in O(1) memory.

Disclosure: I got this from a user in Python Chat after I tried something else... less elegant.

Solution

def range_intersection(*ranges):
    ranges = set(ranges)  # `range` is hashable so we can easily eliminate duplicates
    if not ranges: return
    
    shortest_range = min(ranges, key=len)  # we will iterate over one, so choose the shortest one
    ranges.remove(shortest_range)          # note: `range` has a length, so we can use `len`
    
    for i in shortest_range:
        if all(i in range_ for range_ in ranges): yield i  # Finally, `range` implements `__contains__`
                                                           # by checking if an iteger satisfies it's simple formula

Testing

OP's problem

x = range(1,10)
y = range(8,20)
list(range_intersection(x, y))

[8, 9]

My example

limit = 10_000
list(range_intersection(
    range(2, limit, 2),
    range(3, limit, 3),
    range(5, limit, 5),
    range(41, limit, 41),
))

[1230, 2460, 3690, 4920, 6150, 7380, 8610, 9840]