Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks

## The Stick-Cutting Problem

Assume you have a supply of $n$ sticks of various lengths,
say $L_1,\ldots,L_n$,
and you need *$k$ equally long pieces* (as legs for a table; as posts for a fence;
as boards for a shelf…).

What is the *maximal length* of the pieces you can get from these (without using glue)?

The problem is also called *envy-free stick-division problem* since—if we interpret
the length of a stick as its *value*—cutting sticks as above ensures that we can
produce $k$ maximal pieces that we can assign to $k$ players without inducing envy
between them.

## Origins and Applications

This elementary problem has various connections to other problems:

*envy-free cake cutting*, see the stackexchange question that originally got us interested in the problem,- the problem of
*proportional apportionment*, - and it appeared in a programming contest, and
- it is essentially a special case of the problem of
*selection from the (multiset-)union of sorted sequences*. The Frederickson-Johnson algorithm solves the general problem optimally, but can be improved to linear time for the special sorted subsequences arising in the stick-cutting problem

## Our Contribution

We analyze the structure of this problem and show that it essentially reduces to a single call of a selection algorithm; we thus obtain an optimal linear-time algorithm.

The core idea is to compute cheap upper and lower bounds for the cut length $l^\star$ of the $k$ pieces that we eventually use. This allows to reduce the set of lengths that we have to consider to $O(n)$ candidates. Using arguments of Cheng & Eppstein from an algorithm for the apportionment problem, we can find our optimal cut length $l^*$ by selecting the $k$th largest cut-length candidate.

Despite the simplicity of our algorithm, it did not seem to be known before.