efficient interval containment lookup

[Scott David Daniels]

Are these ranges constrained in any way?
Does preprocessing count in the efficiency cost?
Is the long list or the short list fixed while the other varies?
With no constraints the problem is harder.

 > But perhaps there's a way to index this that makes things more
 > efficient?  I.e. a smart way of indexing listA such that I can
 > instantly get all of its elements that are within some element
 > of listB, maybe?  Something like a hash, where this look up can be
 > close to constant time rather than an iteration over all lists...
 > [what] built-in library functions ... can help?
 > any suggestions on this would be awesome. thank you.

If the intervals have a rough size on either side (or both), that could
give you a useful grid for your hashing.

If the total range of the integers in listA is smallish, you could label 
every value in that range with which elements of listA contain that
point.

You could also look for interesting orders of the intervals in listA,
so that you can use the bisect module to get to one end of a range that
will hold all your answers and only check the applicable elements of
the range.

You might also consider how you could set up numpy arrays to test the
set of ranges in listA in a pair of operations.

I hope I haven't helped you with your homework.

--Scott David Daniels
Scott.Daniels at Acm.Org