CODEWITHSUNDEEP
algorithmdata-structuresrangeintervals
Yijie Li
Yijie Li

Reputation: 71

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?

Upvotes: 3

Views: 860

Answers (5)

Dale Wilson
Dale Wilson

Reputation: 9434

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.

Upvotes: 3

amin k
amin k

Reputation: 1700

i understand that you only want to know that is there A or B in your array.you need not to use sort because you just do 2 steps:

1- search that is there A or B in your array.(you can do it in O(n))
2- find minimum and maximum.(you can do it in o(n)).

you can do it completely in o(n),and you can do not it in less than o(n),i examine this for same question in this link.

Upvotes: 0

didierc
didierc

Reputation: 14730

Obviously, if the list is not sorted, then any algorithm constructing an ad hoc structure for range querying will take O(n). Sorting the list will take O(n log n).

Using a set (implemented as a balanced binary tree), will yeld the result in O(log2n), by inserting the lower (or higher) bound of the range, and examining the next (or previous) element (the data structure must support the operation, it's trivial on a binary tree).

A very efficient structure for range querying is B+tree, which let you find a range in O(logbn+k), where b is the rank of the tree (ie. the number of subnodes for each nodes). Note that this will also return the list of elements in the range (for instance as a couple of iterators on the tree dataset).

Another interesting structure is the Van Emde Boas tree, which insert elements in O(log log n). Using the same trick as for the set above, we can find the answer with the same time complexity. See also the X fast trie and Y fast trie.

Upvotes: 1

user2200390
user2200390

Reputation: 11

If the list is sorted, you can find where the smallest element in the range would be placed into the list, and where the largest element in the range would be placed. This would take 2 lg(n) time. If these indices are different, the range intersects the list. Otherwise, I don't know.

Upvotes: 1

abeln
abeln

Reputation: 3759

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.

Upvotes: 4

Related Questions