For variant 2 of this problem, to minimize the messiness in O(n) time and O(1) space, is it sufficient to maximize the number of words on each line, and minimize the number of lines?
EPIJ 16.11 Pretty printing problem variant 2
shenweihui
#2
My guess is similar to yours. Here’s my attempt to prove the correctness, which may be wrong, so take it with a grain of salt.
Let’s say we have n words and two possible ways to break the words into lines where we have m and m-1 lines respectively. Denote the total length of all the words as W and the line length as L. In the case of m lines, the messiness is X=m*L-W-(n-m). Similarly, the messiness for the case of m-1 lines is Y=(m-1)*L-W-(n-m+1). Clearly, X>Y, so we conclude that minimizing the number of lines can lead to the optimal result.
0 Likes