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

[Arnaud Delobelle]

On Feb 1, 11:23 am, Thomas Pani <thomas.p... at gmail.com> wrote:
> 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?

Yours  is O(n^2) and \Omega(n^2).  I think mine is O(max(c, nlogn))
(assuming constant time access for dictionaries, but 'inside' could be
replaced with a list) where c is the number of overlaps.  I'll try to
post a proof later (if it's true!).  So if we are in a situation where
overlaps are rare, it is in practice O(nlogn).

PS: the way I build 'bounds' is awkward.

--
Arnaud