Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images with minimum possible number of guards.
My suggestion for an algorithm:
Place a guard at $x_1+0.5$ then loop from $i=2$ to $i=n$, if image $x_i$ is protected by the previous guard then do nothing, else place a new guard at point $x_i+0.5.$
I proved that my algorithm returns a valid solution, but am stuck on proving that it returns the minimum solution.
I am trying to prove this claim:
Let $s_i$ be the number of guards placed until and including the point $x_i + 0.5$ Then for each i there is an optimal solution which used exactly $s_i$ guards until and including the point $x_i + 0.5.$
I proved this in 3 pages in case the algorithm adds new guard in step $k$, and only now I discovered a HUGE problem in the induction. what if in step $k$ my algorithm didn't add a new guard?
How can I still prove that the optimal solution which is guaranteed for $k-1$ is still valid (I think in some cases it's not and we need to make some changes to it by moving some or all guards...)?