CODEWITHSUNDEEP
pythonrange
Sarah
Sarah

Reputation: 99

check if two integer ranges overlap

I have two ranges, and I want to check if the ranges overlap at all. I've converted the ranges to lists and am checking if one value in the readRegion is in the refRegion, but this is super slow. Is there a more efficient way to do this?

readRegion=[*range(end,start,1)] #this list is always 600 in length
refRegion=[*range(600000,600500,1)] #this range will vary
p=0
for i in readRegion:
    if i in refRegion and p < 10000:
        regReads.append(filteredReads[n])
        p=10000    
    p+=1

Upvotes: 4

Views: 3539

Answers (5)

Joe Ferndz
Joe Ferndz

Reputation: 8508

You can use set to check if the intersection of the two sets result in any value.

For example, you can do something as simple as :

>>> print (True) if set(range(1,100)) & set(range(90,150)) else print (False)
True

>>> print (True) if set(range(1,100)) & set(range(110,150)) else print (False)
False

If you were to convert these into a function, then you will have something like this:

def compare_ranges(x,y):
    return True if set(x) & set(y) else False

compare_ranges(range(1,100),range(110,150))
compare_ranges(range(1,100),range(90,150))

The output of these two will be:

False
True

The first one does not have any values that are common, the second one has values that are common.

You can also use the same function to check for strings or other datatypes.

compare(['a','b','c','d'],['a','c','e','f'])
compare(['a','b','c','d'],['e','f','g','h'])

The output of this will be:

True
False

Upvotes: 0

kennysliding
kennysliding

Reputation: 2977

  1. If your region is always step=1, i.e. 1, 2, 3, 4, 5,

    Simply run a check on your range, i.e. comparing your end and start against your refRegion range, then calculate the difference.

  2. If your region is not necessarily always step = 1, i.e. sometimes 1, 3, 5, 7, 9, given step = 2

    Include the step in your calculation, pointed out by @orlp's answer

  3. If you region does not follow any step at all, such as 1, 5, 11, 31, 99

    Try to use union in set

    readRegion=[*range(end,start,2)] #this list is always 600 in length
refRegion=[*range(600000,600500,1)] #this range will vary
regionUnion = set(readRegion).intersection(set(refRegion))
print(len(regionUnion))

Upvotes: 0

orlp
orlp

Reputation: 117691

Assuming both ranges always have step 1:

a = range(end, start, 1)
b = range(600000, 600500, 1)
overlapping = (b.start <= a.start < b.stop) or (a.start <= b.start < a.stop)

If not, we have to be a bit more general:

def ranges_overlap(a: range, b: range) -> bool:
    if b.start <= a.start < b.stop:
        return (a.start - b.start) % b.step == 0
    if a.start <= b.start < a.stop:
        return (b.start - a.start) % a.step == 0
    return False

Upvotes: 2

Samwise
Samwise

Reputation: 71454

>>> def range_intersect(a: range, b:range) -> range:
...     assert a.step == b.step == 1
...     return range(max((a.start, b.start)), min((a.stop, b.stop)))
...
>>> range_intersect(range(1, 10), range(5, 20))
range(5, 10)

If you want to just check whether the overlap is nonzero, take len of the resulting range:

>>> len(range_intersect(range(1, 3), range(5, 10)))
0

Upvotes: 1

pho
pho

Reputation: 25489

Two ranges overlap if the larger of their start values is less than the smaller of their stop values. This, of course, is if step is equal to 1.

def overlaps(x, y):
    return max(x.start,y.start) < min(x.stop,y.stop)

print(overlaps(range(10, 100), range(94, 200))

Upvotes: 5

Related Questions