Finding overlapping times...

[Neil Cerutti]

On 2007-12-14, John Machin <sjmachin at lexicon.net> wrote:
> On Dec 14, 10:45 am, 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.
>
> Your definition of overlaps appears to be reflexive, so the following
> two results follow automatically.
>
>> 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?
>
> Probably not.
> Just ensure that (a) your time intervals (start, end) obey start <=
> end (b) your list of intervals is sorted, then get stuck in:
>
> # tested no more that what you see
> alist = [(100000, 100010), (100005, 100007), (100009, 100015),
> (100016, 100017), (100016, 100018)]
> n = len(alist)
> for i in xrange(n - 1):
>    istart, iend = alist[i]
>    for j in xrange(i + 1, n):
>       jstart, jend = alist[j]
>       if jstart > iend:
>          break
>       print "Overlap:", i, alist[i], j, alist[j]
>
> After the sort, it looks like O(N**2) in worst case, but you
> could get a few zillion results done while you are hunting for
> a faster algorithm.

Simply printing out the list of overlaps, even if you knew, a
priori, that all elements overlapped, is an O(N**2) operation. So
I don't think a better algorithm exists for the worst case.

-- 
Neil Cerutti
You only get a once-in-a-lifetime opportunity so many times. --Ike Taylor