[chacham15]

As stated this seems really easy. I think it is supposed to be more like Meebo where the users can resize/move every window (i.e. they dont have to be aligned to any boundary) and they recieve a new message. The Meebo software wants to place a new 100x200 window not on top of any existing window. Write the algorithm to determine where to place it. Then generalize the algorithm to WxH. Hard enough? (If not, find an algorithm that does this in linear time)

[anonymoushn]

Is there a linear time solution? The normal solution is O(N^3) in the number of windows (and does not depend on W,H at all).

[rlanday]

Facebook Hacker Cup had a similar problem: https://www.facebook.com/hackercup/problems.php?pid=53250625...

I almost solved it; after screwing around for a while trying to record only one value for each square, I realized you need to store two values for each square. If we’re looking for the upper-left corner we can put a window, each dead pixel/pixel “poisons” all the pixels less than the width of the window to the left of it and the height of the window above it. Then you just do a linear scan over the remaining pixels. I think my problem was that I used too much RAM because I was trying to store the whole 2D grid; you only need to keep one dimension in memory.

You can see people’s submissions here: https://www.facebook.com/hackercup/scoreboard?round=18989011...

[anonymoushn]

This problem is interesting. It doesn't make any sense to use an N^3 solution like the Meebo problem if N can be so large. I haven't looked at any solutions, but it seems like an N*lg N + WH solution would pass.