Fewest Lamps for the Houses
houses lists the positions of houses along a straight road, in no particular order and possibly with repeats. A lamp can stand at any integer position, with or without a house there, and lights every house whose position is within reach of the lamp: every house at a position from p - reach to p + reach, both included, for a lamp at p.
Return the fewest lamps needed so that every house is lit. The fewest number of lamps is unique, so no tie rule is needed. Return 0 when houses is empty.
Example 1
A lamp at 3 lights the houses at 1, 2 and 5; the house at 9 needs a second lamp.
Example 2
A lamp at 2 lights both 0 and 4, since a reach of 2 covers positions 0 to 4.
Constraints
0 <= len(houses) <= 100-1000 <= houses[i] <= 10000 <= reach <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.