A park is putting benches along a straight nature trail. There are viewpoints at positions spots[i] (metres from the trailhead, in no particular order, possibly repeated). A bench can go at any position, including non-integer ones and positions with no viewpoint, and it serves every viewpoint within reach metres of it (distance <= reach).
Write fewest_benches(spots: list[int], reach: int) -> int that returns the smallest number of benches so that every viewpoint is served by at least one bench.
fewest_benches([1, 2, 6, 9, 10], 1) # 3 benches at 2, 7 and 10 (or 2, 6 and 9, ...)
fewest_benches([4, 0, 8], 4) # 1 one bench at 4 reaches 0 and 8
fewest_benches([5, 5, 5], 0) # 1
fewest_benches([], 3) # 0
Constraints: up to 10^5 viewpoints, positions between -10^9 and 10^9, 0 <= reach <= 10^9. Your answer should be O(n log n).
Show hint
sort the viewpoints; the leftmost unserved viewpoint p needs some bench within reach, and putting it as far right as allowed, at p + reach, serves everything any other choice would, so place it there, skip every viewpoint <= p + 2 * reach, and repeat.