Greedy tutorial

Welcome to the Greedy world. The move: take what looks best right now, and never go back.

At each ledge, grab the biggest gem and climb on. It only works when the best pick now can't hurt you later. Make six from coins one, three and four: greedy takes four, one, one. Three coins. Three plus three is only two, so that one needs dynamic programming.

The clue: minimum number of, maximum you can, intervals, or can you reach, where swapping in the greedy pick never hurts.

Often you sort first, or track one value, like the farthest reach. One pass: linear time, or n log n with a sort.

Now let's use it on Jump Game.