On 2007-12-14, John Machin <[EMAIL PROTECTED]> wrote: > On Dec 14, 10:45 am, Breal <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
