Comparing overlapping ranges

Question

I'm going to ask this question using Scala syntax, even though the question is really language independent.

Suppose I have two lists

val groundtruth:List[Range]
val testresult:List[Range]

And I want to find all of the elements of testresult that overlap some element in groundtruth.

I can do this as follows:

def overlaps(x:Range,y:Range) = (x contains y.start) || (y contains x.start)
val result = testresult.filter{ tr => groundtruth.exists{gt => overlaps(gt,tr)}}

But this takes O(testresult.size * groundtruth.size) time to run.

Is there a faster algorithm for computing this result, or a data structure that can make the exists test more efficient?

---

P.S. The algorithm should work on groundtruth and testresult generated with an expression like the following. In other words, there are no guarantees about the relationships between the ranges within a list, the Ranges have an average size of 100 or larger.

(1 to 1000).map{x =>
   val midPt = r.nextInt(100000);
   ((midPt - r.nextInt(100)) to (midPt + r.nextInt(100)));
}.toList

Answer 1

Try an interval tree. Cormen, Leiserson, Rivest and Stein discuss these in (IIRC) chapter 14.

Alternatively, if your lists of intervals are both sorted and the intervals within a list are non-overlapping, then the following algorithm solves your problem in linear time and in a single pass over both lists:

(define interval cons)
(define lower car)
(define upper cdr)

(define (overlap a b)
  (cond ((or (null? a) (null? b)) '())
        ((< (upper a) (lower b))
         (overlap (cdr a) b))
        ((> (lower a) (upper b))
         (overlap a (cdr b)))
        (#t  ;; (car a) and (car b) overlap
             ;; EDIT: there's a bug in the following part.
             ;; The code shouldn't skip over both cars at once,
             ;; since they may also overlap with further intervals.
             ;; However, I'm too tired to fix this now.
         (cons (interval (max (lower a) (lower b))
                         (min (upper a) (upper b)))
               (overlap a b)))))

(I hope you can read Scheme :)