Java exercise

[Stefkari24]

Can anyone solve me this
We are given a street with N possible positions on which we can put a light. A single light will illuminate its own position and 2 more positions to the left and 2 more to the right of it. Our task is to illuminate the street with the minimum possible lights. Not all possible positions must contain light.
Input: The first number in the input is the number of possible positions to put a light bulb N and the length of the street M, then in the next line are the possible positions on which we can put a light.
Output: The minimum lights we need to illuminate the street.
For example:
Input
Result
n=5 m=5
for posisions 1 2 3 4 5
answer 1 lamp
n=3 m=10
for posisions 3 8 9
answer 2 lamp

 

[Blue JProgramme]

Sorry, I don't know, I am also want to ask the code of Shoelace Program, se my thread

I think that exercis would use selection

 

[WhiteCube]

My first thought was to test every combination of switches. Find the combination that lights the whole area and uses the least number of lit bulbs.

Which would work, but feels like overkill.

On the other hand, I think this would work.

Start in position 1.

Walk forward until your position is dark. Lets call that position x.

You need to switch on a light, at position x, x+1 or x+2.

If there is a bulb at x+2, its the best choice, because it doesn't waste light behind you, and reaches the furthest in front of you.

If there is no bulb at x+2, try x+1, if there is no bulb at x+1, you must use x.

Switch on the best bulb and continue walking, until you're in darkness again.

Repeat.

I could be wrong.

 

[WhiteCube]

I tried a few tests, and I found a case where the light you need to switch on is behind you.

001100

So you need to switch on a light, at position x+2, x+1, x, x-1, or x-2. Whichever is greatest.