I have the following assignment:

Design (in detail) and analyze a data structure that will hold a set of n weighted intervals of the real line, that is, a set of triples (a, b, w) such that a, b ∈ ℜ and a < b and w is a positive integer. Think of a as the left endpoint and b the right endpoint of a segment of the real line. A query to this data structure will consist of a value z ∈ ℜ and will ask for the heaviest interval containing z. Your data structure should require O(n log n) preprocessing time, and then O(log n) time to process a query.

And my idea is to store the triples in a red-black tree indexed by their $a$ value. So, creation of the data structure would take O ( n log n ), as required.

Then, for querying the data structure, my idea was to do an in-order traversal of the tree, starting with the minimum $a$ value in the tree and continuing until an $a$ value is encountered that is equal to or greater than $z$. Of course, the idea would be to keep track of the heaviest triple seen as you go, returning it.

The query process takes worst case O ( n ) time--say, when z is larger than all $a$ in the tree.

But then, $b$ must also be greater than $z$. So, my algorithm isn't even right to begin with.

I imagine we're supposed to use something like Bentley and Shamos' algorithm for finding closest pairs in k-dimensional space or line-sweeping algorithms.

Any insights and guidance would be appreciated.

  • Can you credit the source of your assignment? – D.W. Nov 11 '17 at 2:14

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.