# Checking if ranges cross paths - Python

TAGS :
Viewed: 1 - Published at: a few seconds ago

#### [ 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]
b = lst[i]
x = lst[j]
y = lst[j]

#both of these conditions mean that they cross
if x &lt; a and b &gt; y:
return True
if x &gt; a and b &lt; 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?

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 < b 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 < b 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.

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)