The Skyline algorithm for packing 2D rectangles

Very fun. I wonder if a heap could improve the performance of the "loop through the skyline in order to find the best candidate location" step. (I think it would improve the asymptotic time, if I'm understanding the algorithm correctly, but obviously the real performance is more complex).

With some clever bit twiddling hacks, you might be able to avoid the loop entirely.