Greedy line breaking commits each line after filling it with the longest available fitting prefix of the remaining input. In a fixed-width model, the input consists of ordered, indivisible typesetting boxes, a common typesetting line width , and nonnegative fixed word spacing. Assume every individual box fits. The greedy algorithm scans forward, adds the next item if it fits, and otherwise starts a new line. Incrementally maintaining the used width gives time complexity for input boxes.
This rule minimizes the number of lines under these assumptions. To see why, let be the last item covered by the first greedy lines, and the last item covered by the first lines of any feasible alternative. After a layout finishes, take its endpoint to remain for subsequent indices. The first greedy line reaches at least as far as the alternative's first line. Suppose . If the greedy layout has already reached , the next inequality is immediate. Otherwise, removing the alternative's already covered items from its next line leaves a fitting suffix, because widths and gaps are nonnegative. The next greedy line can reach at least that endpoint. By mathematical induction,Thus an alternative cannot finish in fewer lines.
Line count and paragraph appearance are different objectives. With widths , gap 1 and width 7, greedy grouping has lengths . The alternative also uses three lines. The line breaking with squared slack cost model assigns cost 20 to this alternative and 26 to the greedy layout when the final line is free. The line breaking diagram shows the two layouts. Global paragraph costs can justify dynamic programming even when greedy packing already uses the minimum line count.
The fixed-width assumptions matter when applying this result. Hyphenation introduces additional break opportunities, while adjustable typesetting glue changes how a candidate line fits. Those choices belong to richer layout models such as the Knuth-Plass line-breaking algorithm.
New to topics? Read the docs here!