# How to prove the my greedy algorithm for placing guards?

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...)?

• Do you mean that the $n$ images are placed on a line? – phan801 Jun 8 at 13:12
• @phan801 yes I do – coolmo Jun 8 at 15:59
• Are you sure, you want to prove "minimal" and not "minimum"? – Inuyasha Yagami Jun 8 at 17:03
• Updated thanks for your note :) – coolmo Jun 8 at 18:26
• I can't tell what kind of answer you are looking for. I'm not sure how we're supposed to answer "What if?" Also that doesn't sound like a question for us to answer; it sounds like you identifying a flaw in your proof. I suggest spending some more time on identifying what the question you want answered is, and then organizing your post so that comes across clearly with no possibility of confusion. The easier you make it for readers to understand what you are asking, the more likely that you get a useful answer. – D.W. Jun 8 at 20:42

Call an image critical if the greedy algorithm places a guard $$0.5$$ after it.
The algorithm ensures that each critical image is more than $$1.5$$ away from the previous critical image (except the first image, before which there is no image). That means any two critical images are more than $$1.5$$ apart.
Since a guard covers an interval of length $$1.5$$, it can cover at most one critical image. So, any solution must place at least as many guards as critical images. The greedy algorithm places exactly one guard for each critical image. So, the greedy algorithm is optimal.$$\quad\checkmark$$