Determing whether two ranges overlap

[Magnus Lycka]

Fredrik Lundh wrote:
>     def overlap(a, b):
>         return a[1] > b[0] and a[0] < b[1]

Assuming that x[1] can't be smaller than x[0], this
is the right way to compare two ranges. Well, I guess
you need to figure out the borderline cases. Is it
a[1] > b[0] or a[1] >= b[0] which is relevant?

Anyway,  if we have N ranges and N is big, we'll get
lots of comparisions: N*(N-1)/2.

For large values of N, it might be better to somehow
cache/aggregate the intervals if this makes it possible
to make this into an N*M comparision where M is smaller
than (N-1)/2....

E.g, with discrete values for the intervals such as with
(10, 15), one might consider something like (untested):

hits = sets.Set()

for interval in intervals:
     for i in range(interval[0], interval[1]+1):
         if i in hits:
             raise ValueError('%s overlaps previous interval.'
                               % interval)
         hits.add(i)

E.g. if we have 1000 intervals where the average size of
an interval is 10, you get 10000 "i in hits" and "hits.add(i)"
instead of 499500 'a[1] > b[0] and a[0] < b[1]'.

As always, it's good to measure...assuming you have fairly
realistic data to test with.