Finding overlapping times...

[John Machin]

On Dec 14, 12:05 pm, Dave Hansen <i... at hotmail.com> wrote:
> On Dec 13, 5:45 pm, Breal <sean.be... at cox.net> wrote:
>
> > I have a list that looks like the following
> > [(100000, 100010), (100005, 100007), (100009, 100015)]
>
> > I would like to be able to determine which of these overlap each
> > other.  So, in this case, tuple 1 overlaps with tuples 2 and 3.  Tuple
> > 2 overlaps with 1.  Tuple 3 overlaps with tuple 1.
>
> > In my scenario I would have hundreds, if not thousands of these
> > ranges.  Any nice pythonic way to do this?
>
> What are you going to do with the result?  Do you need to know if
> there are any overlaps?  The number of overlaps?  Given any particular
> range, what ranges overlap?
>
> There's really no way, other than to compare each range.  Note that
> the relationship is symmetric, so you can save half you work.  A
> simple-minded approach might be
>
> ---
>
> def overlaps(t1, t2):
>     return (t2[1] >= t1[0]) and (t2[0] <= t1[1])
>
> in_data =  [(100000, 100010), (100005, 100007), (100009, 100015)]
>
> while (len(in_data) > 1):
>     target = in_data.pop(0)

A tad excessive:

pop(0) is O(N)
pop() is O(1)

Pythonic and likely to be faster, Take 1:

while in_data:
    target = in_data.pop()

Pythonic and likely to be faster, Take 2:

while 1:
    try:
        target = in_data.pop()
    except IndexError:
        break

>     for test in in_data:
>         if overlaps(target,test):
>             print "%s overlaps with %s" % (repr(target),repr(test))

Cheers,
John