FunctionRacerProblemsRace

Fewest Lamps for the Houses

EasyGreedyPython, JavaScript, TypeScript, Java, C++

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

houses [1,5,9,2]
reach 2
returns 2

A lamp at 3 lights the houses at 1, 2 and 5; the house at 9 needs a second lamp.

Example 2

houses [0,4]
reach 2
returns 1

A lamp at 2 lights both 0 and 4, since a reach of 2 covers positions 0 to 4.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems