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...
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 ? :-))
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?