Finding overlapping times...

[Scott David Daniels]

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....

In relation to a similar (but not identical) problem, that of
finding nested scopes and the associated name tables, I found
the following order useful:
     def range_key(pair):
         return pair.least, -pair.greatest

     somelist.sort(key=range_key)

If you sort this way, you get nested elements in a quite useful
order for 1-pass scanning.  Nested elements show up in order of
nesting (outer to inner), so a single scan of the result can
reveal nesting violations.

-Scott David Daniels
Scott.Daniels at Acm.Org