1

Given a container which width is W and height is H, I'd like to fit N squares of maximal size S in it.

Example 1

W = 240
H = 210
N = 7
S = 70

enter image description here

Example 2

W = 200
H = 230
N = 23
S = 40

enter image description here

How would you calculate S from W, H, and N in O(1)?

Misha Moroshko
  • 111

1 Answers1

0

Assume $W \ge H$ (otherwise swap them). If you could pack them perfectly the area would say $S=\sqrt{\frac {WH}N}$. If you use that side you get $m=\lfloor \frac HS \rfloor$ across the height.
Start with $m+3$ (just a guess for safety) across the height, compute
Side that fits in height $\frac H{m+3}$
Number required in width $n=\lceil\frac N{m+3}\rceil$
Side that fits in width $\frac Wn$ Now decrease the number across the height and recompute the sides It should increase and then start to decrease. Report the maximum.

Ross Millikan
  • 374,822
  • It this an O(1) solution? How many checks we need to perform in the worst case before we can stop? – Misha Moroshko Jul 28 '18 at 05:36
  • I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $\frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make. – Ross Millikan Jul 28 '18 at 13:57