I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally:
Problem: Given N equal-sized squares and a rectangle with width W and height H, find out the maximum size of the squares L such that the squares fit inside the rectangle in such a way that their sides are orthogonal to the rectangle sides.
So far, I think we have a
O(sqrt(N)) solution, in which we assume
W>H, start by trying to place all squares in a single row, then in two rows and so on, until we get to
O(sqrt(N)). For formally, let
nRows be a variable from 1 to
nCols = ceil(N/nRows) and then do
L = min(H/nRows, W/nCols).
I'm not completely sure the idea above is optimal. I was also wondering if we can solve this problem in
I've tried looking for orthogonal square packing, but the problem seems a bit different (or could we easily reduce on to another?)