CODEWITHSUNDEEP
pythonrangeintersection
sten
sten

Reputation: 7486

Fastest way to check if ranges only intersect, but not subsume

Let's say I have two ranges (x1,x2) and (z1,z2). What is fastest way to check if they intersect?

 if 
 #case: (2,4), (3,6)
 x1 > z1 < x2 and (z2 < x1 or z2 > x2)
 or
 #case: (2,4) , (1,3)
 x1 > z2 < x2 and (z1 < x1 or z1 > x2)
 or
 #case: (3,6), (2,4)
 ............. reverse(1) x <--> z
 or
 #case: (1,3), (2,4)
 ............. reverse(2) x <--> z

BTW containing one range in the other is OK, for example

 (2,5) , (3,4)
 (2,5) , (3,5)
 (2,5) , (2,4)

(this makes the question not a duplicate. In addition the conditions are <, > rather than >=, <=. And one more I expect input ranges to be also unordered, for example (x2,x1),(z2,z1) ; (z1,z2),(x1,x2) )

But this, for example, does not count as intersection:

 (2,5), (2,5)

What is a faster way with less checks?

NOT a duplicate ... here is the solution :

def olap(x1,x2,z1,z2):

    if x1 == x2 or z1 == z2 : return True
    if x1 == z1 and x2 == z2 : return True

    if x1 > x2 : x1,x2 = x2,x1
    if z1 > z2 : z1,z2 = z2,z1
    if x1 > z1 or x2 > z2 : z1,z2,x1,x2 = x1,x2,z1,z2

    return x1 < z1 < x2 and (z2 < x1 or z2 > x2)

Upvotes: 1

Views: 143

Answers (1)

Nikos Athanasiou
Nikos Athanasiou

Reputation: 31597

Simplest check is to verify a property of intersecting intervals: None of the leftmost endpoints (smaller) can be higher than a rightmost endpoint (higher).

 x1        x2
a ------------              if x1 > y2: a would be to the right of b            
       b ----------------   if y1 > x2: b would be to the right of a
           y1           y2

def overlap(x1, x2, y1, y2):
    """ Overlap means neither of the intervals 
        is "to the right or left" of the other.
    """
    return x1 <= y2 and y1 <= x2

Upvotes: 1

Related Questions