Why does a greedy solution work for this problem?

  • 3

    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?

  • 0

    I am wondering this too. Why adding 7 makes 7~13 covered? How to prove it for all general case? Especially during interview.

  • 0

    because before patching 7, 1~6 can already be covered. With 7 patched, now you are able to get 1+7, 2+7, 3+7,... 6+7. So next you just need to test whether 7+7 can be reached.

  • 0

Log in to reply

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