472,992 Members | 3,343 Online

# Finding overlapping times...

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?

Thanks.
Dec 13 '07 #1
7 3140 You should give a more real data set (maybe 20 various pairs so that all
scenarios can be seen) and the output you want.

Breal 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?

Thanks.

--
Shane Geiger
IT Director
National Council on Economic Education
sg*****@ncee.net | 402-438-8958 | http://www.ncee.net

Leading the Campaign for Economic and Financial Literacy

Dec 14 '07 #2
On Dec 13, 3:45 pm, Breal <sean.be...@cox.netwrote:
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?
Sure.

Write down under what conditions two tuples of numbers will overlap.
Be specific.

(Hint: two numbers can be equal, less than, or greater than each
other. That's 3 conditions. Then you can compare the first of the
first tuple to the first of the second tuple, or the first to the
second, or the second to the first, or the second to the second.
That's 4 conditions. 3x4=12 so you have 12 possible conditions when
comparing two tuples of two numbers. Describe what the result should
be for each one. Being graphical will help you get it right.)

Once you have that written down, translate it to python.

In python, write a loop that goes through each item in the list and
compares it to every other item. Remember which items compare
favorably by storing them in a list.

When the loop finishes, you should have a list of all the pairs that

Since this sounds like a homework assignment, the rest is left as an
Dec 14 '07 #3
On Dec 14, 10:45 am, Breal <sean.be...@cox.netwrote:
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
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
Dec 14 '07 #4
On Dec 13, 5:45 pm, Breal <sean.be...@cox.netwrote:
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 >= t1) and (t2 <= t1)

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
Dec 14 '07 #5
On Dec 14, 12:05 pm, Dave Hansen <i...@hotmail.comwrote:
On Dec 13, 5:45 pm, Breal <sean.be...@cox.netwrote:
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 >= t1) and (t2 <= t1)

in_data = [(100000, 100010), (100005, 100007), (100009, 100015)]

while (len(in_data) 1):
target = in_data.pop(0)

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
Dec 14 '07 #6
Hi Breal
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?
This may be of no help, but....

In 1995 I wrote a C library to do some stuff like this. You're welcome to
the code. It might give you some ideas, or you might want to wrap it for
Python. If you did that, and had additional energy, you could release the
result to the Python community.

As someone said, how/what to do depends what you want to do with the
resulting data structure once you've processed the inputs.

In my case I wanted to be able to read in a large number of ranges and be
able to answer questions like "is X in the range?". I'm pretty sure I made
it possible to add ranges to ignore (i.e., that punch holes in an existing
range). I'm also pretty sure I'd have made this run in n log n time, by
first sorting all the lower bounds (and maybe sorting the upper ones too)
and then walking that list.

One use case is e.g., for a printer program command line:

print --inc-pages 40-70 --exc-pages 51-52 --inc-pages 100-120

which could use the library to step through the range of pages in a doc and
easily check which ones should be printed. There are lots of other uses.
Lookup time on those queries was probably log n where n is the resulting
number of range fragments once the processing (merging/splitting) of the
command line was done.

I don't remember, but it took me several days to write the code, so it
wasn't completely trivial.

I can't offer help beyond the code I'm afraid - I have too much other stuff
going on.

Terry
Dec 14 '07 #7
On 2007-12-14, John Machin <sj******@lexicon.netwrote:
On Dec 14, 10:45 am, Breal <sean.be...@cox.netwrote:
>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
>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
Dec 14 '07 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 1 by: André Søreng | last post by: With the re/sre module included with Python 2.4: pattern = "(?Pavi)|(?Pavi|mp3)" string2match = "some string with avi in it" matches = re.finditer(pattern, string2match) ....... 11 by: Max M | last post by: I am writing a "find-free-time" function for a calendar. There are a lot of time spans with start end times, some overlapping, some not. To find the free time spans, I first need to convert the... 3 by: Phil Sandler | last post by: All, I have a table with start and end dates/times in it, and would like to be able to calculate the number of hours represented, accounting for overlapping records. Note that I am looking... 0 by: Chris Q. | last post by: I am creating a custom control that contains a list view with dates and times. I need to make sure that times do not overlap. I would like the control to determine if the overlap is occuring with the... 5 by: giampiero mu | last post by: hi everyone my target is implement a function controlla(string - a binary string-) that check if there is in a string two equal not overlapping subsequences at least of length limitem: my... 11 by: corsin | last post by: Hello everybody! I've been trying to find a way to create a MySQL query to find overlapping intervals, but no success so far. I've the following table as an example: Src Dst Start_time End_time... 0 by: richard12345 | last post by: Hi Guys I have problem with site I am building. The sidebar with menu and other thinks is overlapping footer. The footer move with the content and but it dos it dos not move with the sidebar. ... 2 by: manugm1987 | last post by: