efficient interval containment lookup

[Robert Kern]

[Apologies for piggybacking, but I think GMane had a hiccup today and missed the 
original post]

[Somebody wrote]:
>> suppose I have two lists of intervals, one significantly larger than
>> the other.
>> For example listA = [(10, 30), (5, 25), (100, 200), ...] might contain
>> thousands
>> of elements while listB (of the same form) might contain hundreds of
>> thousands
>> or millions of elements.
>> I want to count how many intervals in listB are contained within every
>> listA. For example, if listA = [(10, 30), (600, 800)] and listB =
>> [(20, 25), (12, 18)] is the input, then the output should be that (10,
>> 30) has 2 intervals from listB contained within it, while (600, 800)
>> has 0. (Elements of listB can be contained within many intervals in
>> listA, not just one.)

Interval trees.

http://en.wikipedia.org/wiki/Interval_tree

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco