Cutting equal sticks from different sticks
The first core observation to solving this problem is that the feasibility of a cutting length $l$,

$\qquad\displaystyle \operatorname{Feasible}(l) = \biggl[\, \sum_{i=1}^n \Bigl\lfloor\frac{L_i}{l} \Bigr\rfloor \geq k \,\biggr]$,

is piecewise-constant, left-continuous and non-increasing in $l$. Since the number of necessary cuts behaves similarly, finding the optimal length is just

$\qquad\displaystyle l^{\star} = \max \{ l \mid \operatorname{Feasible}(l) \}$.

Furthermore, as the other answers have proposed, all jump discontinuities have the form $L_i/j$. This leaves us with a discrete, one-dimensional search problem amenable to binary search (after sorting a finite set of candidates).

Note furthermore that we only need to consider the $L_i$ that are shorter than the $k$-largest one, since that one is always feasible.

Then, different bounds on $j$ lead to algorithms of different efficiency.


$1 \leq j \leq k$ results in a search space of quadratic size (in $k$),
$1 \leq j \leq \lceil k/i \rceil$ in a linearithmic one (assuming the $L_i$ are sorted by decreasing size), and
slightly more involved bounds in a linear one.


Using this, we can solve the proposed problem in time $\Theta(n + k \log k)$ and space $\Theta(n + k)$.

One further observation is that the sum in $\mathrm{Feasible}$ grows in $l$ by $1$ for each candidate $L_i/j$ "passed", counting duplicates. Using this, we can use rank selection instead of binar search and obtain an algorithm that runs in time and space $\Theta(n)$, which is optimal.

Find the details in our article Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts (by Reitzig and Wild, 2015).