# Prove Correctness of Algorithm? – Computer Science Stack Exchange

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?