How to identify which numbers in a list are within each others' range

[Thomas Pani]

Arnaud Delobelle wrote:
> 
> This is definitely the best way:
> 
> from itertools import chain
> 
> def overlaps(lst):
>     bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)))
>     inside = {}
>     for x, i in sorted(bounds):
>         if inside.pop(i, None) is None:
>             for j, y in inside.iteritems():
>                 if y != x: yield i, j
>             inside[i] = x

Why not just

def overlaps(lst):
    for i,x in enumerate(lst):
        for j,y in enumerate(lst):
                if i != j and x[1] > y[2] > x[2]:
                    yield i,j

It's still n^2. Or am I missing something?

Cheers,
thomas