# Finding the heaviest interval in a one-dimensional space containing a point

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