#### [ 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:])
```