Fewest Towers to Cover Every Crossing
Border crossings sit at known integer positions along a line. A tower placed at any position x covers every crossing in [x − r, x + r]. Return the fewest towers that cover every crossing.
crossings = [1, 2, 3, 10], r = 1 -> 2 (towers at 2 and 10) crossings = [5, 5, 7], r = 0 -> 2 crossings = [1, 4, 7], r = 3 -> 1 (one tower at 4)
The positions are unsorted and may repeat. No crossings need no towers.
Hints
Hint 1
Sort the crossings. The leftmost uncovered crossing has to be covered by some tower — and placing that tower as far right as possible can only help the crossings after it.
Hint 2
So each tower goes at leftmost + r, and it covers everything up to leftmost + 2r. Skip past those and repeat.