Expert · Greedy algorithms · 246 of 264
Fewest jumps
Each number says how far you may jump forward from that position. Starting at the first position, what is the fewest jumps to reach the last? Print -1 if you cannot.
Input: n, then n whole numbers (0 or more) on one line. Output: the fewest jumps.
Examples
Input
5 2 3 1 1 4
Output
2
Input
5 3 2 1 0 4
Output
-1
Input
1 0
Output
0
One more test checks other inputs when you press Check.
Stuck? The idea behind greedy algorithms
Take the best-looking choice at each step and never go back: sorting first usually makes the best choice obvious.
It works only when a local best choice can't spoil the whole answer; for meetings, choosing the one that ends earliest leaves the most room.
meetings = [(1, 4), (3, 5), (0, 6), (5, 7)]
end, count = -1, 0
for s, e in sorted(meetings, key=lambda m: m[1]):
if s >= end:
count += 1
end = e
print(count)Watch for: Sorting by the wrong thing (start instead of end) gives a plausible but wrong answer: try a small case by hand.