Finding overlapping times...

[Terry Jones]

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