math - Max square size for unknown number inside rectangle

Question

If I have a set of tiles (squares) which can be any number and they are to fill a container (rectangle) of an unknown size how do I work out the maximum size of the tiles without having any of them overlap.

So if I have 2 tiles and the rectangle is 100 * 100 then the max tile size is 50 * 50. This would also be the max size of tile if there was 3 or 4 tiles for this size of rectanlgle, which just so happens to be a square in this example.

If the rectanlge was 100 * 30 and I had 2 tiles, the max size of the square would be 30 * 30, if I have 4 tiles the max size would be 25 * 25.

How can I do this programatically without hogging the processor by going through every possible combination.

---

I try to summarise a bit better, I have a:

rectangle/bounding box that I need to fill as much as possible without the tiles overlapping.

I know the height and width of the rectangle (but this can change during runtime).

I have X number of tiles (this can change at run time), these are squares.

None of the tiles should overlap, what is the maximum size that each tile can be. They are all to be the same size.

Answer 1

Conceptually:

• start with 1 square
• For each additional square, if you don't have room in your grid box so far, shrink the existing box just enough to make room for an additional row or column.

pseudocode: given M x N rectangle to fill with K squares

// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
  if M/(h+1) >= N/(w+1)
    h=h+1
  else
    w=w+1
  endif
  maxsquares=h*w
  size=min(M/h,N/w)
done
print size

There are probably faster ways to jump to the answer for very large K, but I can't think of them. If you know that M and N are integers, there may be even faster methods.