This is a real-world application, not a student assignment.
- Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.
- The boxes have the same height, but variable width.
- When a box doesn't fit, it should wrap to the next line (just like text).
- After that, we fix the number of lines, and then lay out the boxes again so that the lines have a more balanced width, which means they try to be the same width, as much as possible.
The input is, simply:
double colWidth = …; List<double> boxWidths = [ … ];
And the output could be:
List<int> result = [ … ]; // Number of boxes in each line. double minWidth = …;
An example: Suppose the column has width = 11, and 5 boxes have widths [2, 3, 5, 2, 1], then the layout is this:
| ** *** ***** | | ** * |
This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).
Now we have to lay them out again in 2 lines, to achieve balanced width:
| ** *** | | ***** ** * |
The result is 2 boxes in the first line, and 3 boxes in the second line:
List<int> result = [2, 3]. Widths are now 5 and 8. Difference is 3, and
minWidth is 8.
Please note, we cannot change their order. If we could, then the difference would be 1 and
minWidth would be 7:
| ** *** * | | ***** ** |
What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.