[wiz21]

Ahhh read too fast :-( Crucial sentence is "Fortunately, we know about a data structure which can keep track of an active set of integer-keyed objects and return the highest one in O(logn) time: a heap."

But then again. If I read well, he wants to 1st sort the points, 2 iterate over them and using the heap. So we have n log n for the sort and n * n log n for the heap use.. Basically (1+n) n log n (or i'm still tired ? :-))

[brianpgordon]

The uses of the heap are:

1. Peek the root of the heap to find the tallest rectangle in the active set. This is a constant time operation.

2. Add a new rectangle to the active set. This is a O(log(n)) operation.

3. Remove a rectangle from the active set. This is a O(log(n)) operation if you use something like a hash table to locate the element in the heap.

Each rectangle is added once (at its left edge) and removed once (at its right edge). The root of the heap is peeked on every critical point. All together, that makes the algorithm O(n log n).

Or am I missing something?