Q:

How to test if a integer range has overlap with an integer list?

For example:
we have a list:
1 2 3 7 8 9 11 12

We need to check if a range (A,B) overlaps with the list, e.g range (4, 6) does NOT overlap with the list , range ( 10, 12) and range(5,9) do overlap with the list.
I know we can put the list in a hashSet, then we just check if any element in range appears in that set. This costs O(N). N is the length of the range. Is there a better algorithm to solve this problem? I know there's an interval tree data structure, but I don't quite understand it. Can that structure solve this problem in logN?

A:

It seems like the list is sorted; if it's not already, then sort it first.
Let R = (start, end) be the range we want to check to see if it overlaps.
We can binary search the positions of start and end on the sorted list:

if start and end show up consecutively on the list, then they don't overlap

e.g.

1 2 3 4 6 7 8 9 11 12

otherwise, there's an element of the list that is between them, so the range overlaps

behold:

1 2 3 7 8 9 10 11 12

This is O(log N), where N is the number of elements in the list.

A:

If the list is not sorted:
O(M) where M is the # of items in the list is to iterate thru the list checking each item to see if  low <= item <= high.

Alternative if the domain is "reasonably" bounded:
Represent the list as a bit vector.  Represent the range as a bit vector (the on-bits in this vector will be contiguous) then 'and' the vectors to see if there is a bit in common.

