Finding overlapping times...

[Dave Hansen]

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)
    for test in in_data:
        if overlaps(target,test):
            print "%s overlaps with %s" % (repr(target),repr(test))

---

If you want to save the information for later retrieval, you could
build a dictionary with the ranges as keys:

---
ovr_map = {}

while len(in_data) > 1:
    target = in_data.pop(0)
    for test in in_data:
        if overlaps(target,test):
            if ovr_map.has_key(target): ovr_map[target].append(test)
            else: ovr_map[target] = [test]
            if ovr_map.has_key(test): ovr_map[test].append(target)
            else: ovr_map[test] = [target]

for target in ovr_map.keys():
    for test in ovr_map[target]:
        print "%s overlaps with %s" % (repr(target),repr(test))
---

I don't know that there isn't a more Pythonic way, I'm not much of an
expert.  HTH,

   -=Dave