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 minimal
number of guards.
My suggestion for an algorithm:
Place guard in $x_1+0.5$ then do loop from $i=2$ to $i=n$, if image $x_i$ protected by previous guard then do nothing, else place a new guard at point $x_i+0.5$
I proved that my algorithm returns valid solution, but stuck on proving that it returns minimal solution.
I am trying to prove this claim:
let $s_i$ be the point where guard $i$ was placed by my algorithm, then for each $i$ there is a minimal solution which placed guards in points $s_1, … , s_i$
I went for induction and proved base case for $i=1$ But stuck on later steps. Any help?