Finding overlapping times...

[John Machin]

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.

Cheers,
John