[frownie]

is it me or the algorithm suggested at the end degenerates if the rectangles are organized as the steps of a stair and each of them extends to the rightmost position ? In that case it degenerates because the heap manipulation degenerates...

[brianpgordon]

I don't think so. No matter what shape the problem is in, there are always exactly n inserts and n deletes to the heap. Those are O(log n) operations, and there are 2n of them, so it's O(n log n).

[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?