Why does a greedy solution work for this problem?


  • 2
    R

    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?


  • -3
    A

    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".


  • 0
    R

    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.


  • 16

    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.


  • 0
    T

    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:)


  • 0

    @dietpepsi said in Why does a greedy solution work for this problem?:

    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?


  • 0
    P

    @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


Log in to reply
 

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