This is the one dimensional case of a more general problem I posted, linked here.
Given an interval of length $n$, define a cut as a point somewhere in the interval. In expectation, how many uniformly sampled cuts are needed to partition the interval into segments of unit length or less?
The obvious lower bound is $O(n)$ and I speculate the answer is $O(n\log(n))$, but I don't really know how to approach this question. Has this problem or a similar problem been tackled?
You need at least one point in each interval of the form $(k, k+1)$ for whole $k$. The coupon collector problem argument says this takes $n \log n + \gamma$ points. If you get one point in every interval of the form $(k, k+\frac 12)$ and $(k+\frac 12, k+1)$ that is guaranteed to be sufficient. The same coupon collector argument says this takes $2n \log(2n) + \gamma$ points, which is also $O(n \log (n))$ so we have the big-O class of the answer.
Thanks to Jorge Fernández Hidalgo for the half unit idea.