# Why does a greedy solution work for this problem?

• I see in many solutions posted here, the strategy is to patch the next missing number itself:

For example, with [1, 2, 3] and N=20, I get 1-6 covered, and I patch 7.

Yes, 7 would push the frontier the furthest (to 13), but if I choose to patch 4 instead, maybe a 4 may come in handy when I need to make other numbers down the road?

Why is this choice 7 optimal? Can any provide a solid proof?

• As I see it, the point of not using a 4 is straight forward. As 1 + 3 gives a 4, there is no point in introducing another "4".

• what if the number needs two 4s, 1+3 gives you one 4, having another 4 is useful.

I know it is a bad example. But what I want is a proof that choosing the "currently missing" number is optimal strategy.

• You already covered 1-6, and the missing number is 7. Adding 7, you will cover 1-13. Therefore, 7 is optimal for N = 7~13. Note that here by optimal we mean that we need the minimum number of patches (which is 1).

4 is equally optimal for N = 7~10, but not for N = 11 to 13.

The proof is quite straightforward by induction or contradiction.

What we want to prove is

If the greedy algorithm needs to patch `k` numbers to cover 1~N, it is impossible to patch less than `k` numbers to do the same.

Proof by contradiction

For a given `N` the `k` patches found by greedy algorithm is M1 < M2 < ... < Mk <= N.
If there is another set of patches X1 <= X2<= ... <= Xk', with `k' < k`, then we have

X1 <= M1 (otherwise M1 is not covered)

X2 <= M2 (otherwise M2 is not covered)

.

.

.

Xk' <= Mk' (otherwise Mk' is not covered)

We can see that since M1 M2... Mk' is not enough to cover Mk, therefore X1, X2,..., Xk' is also not enough to cover Mk <= N. This contradicts the fact that X covers 1~N.

• Hi, could you explain a little more why:
X1 <= M1 (otherwise M1 is not covered)

X2 <= M2 (otherwise M2 is not covered)

.

.

.

Xk' <= Mk' (otherwise Mk' is not covered)??
Thanks a lot:)

• X2 <= M2 (otherwise M2 is not covered)

I think this proof is still not rigorous enough: M2 isn't necessarily uncovered, it could be covered by X1 (unless we prove this case is impossible). Ideas?

• @dietpepsi I have tried to prove it using Greedy stays ahead paradigm. Please see if it looks ok.
https://discuss.leetcode.com/topic/35494/solution-explanation/57

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.