[ Checking if ranges cross paths ]

I wrote the following method to check if a list of ranges cross paths. Another way of saying this is that the ranges are not nested.

def check_ranges(lst):
    for i in range(len(lst)):
        for j in range(i+1,len(lst)):
            # (a,b) and (x,y) are being compared
            a = lst[i][0]
            b = lst[i][1]
            x = lst[j][0]
            y = lst[j][1]

            #both of these conditions mean that they cross
            if x < a and b > y:
                return True
            if x > a and b < y:
                return True
    return False

The first should return false and the second true.

check_ranges([(7,16),(6,17),(5,18),(4,19)])
check_ranges([(5,16),(6,17),(5,18),(4,19)])

It works as it is now, but it seems really inefficient. Does anyone now if this is a common problem or if there is a more efficient solution?

Answer 1

You could sort, which will put at least the starting points in sorted order. Then you only really need to check the endpoint against the previous entry; it should be smaller:

from itertools import islice

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def check_ranges(lst):
    return any(a[1] < b[1] for a, b in window(sorted(lst)))

I'm using the window example tool from an older itertools documentation page here to create the sliding window.

This implementation returns:

>>> def check_ranges(lst):
...     return any(a[1] < b[1] for a, b in window(sorted(lst)))
... 
>>> check_ranges([(7,16),(6,17),(5,18),(4,19)])
False
>>> check_ranges([(5,16),(6,17),(5,18),(4,19)])
True

It is not entirely clear if matching end points would be a problem or not; if they are not, then you could change the < to a <= test instead.

Answer 2

I'm not sure about the algorithm which you are using to detect "crossover", but you could simplify your code using a comprehension and any:

return any((x<a and b<y or x>a and b<y) 
            for i,(a,b) in enumerate(lst) 
            for (x,y) in lst[i:])