0
Challenge · 68Greedy, Bits & Math
Greedy: when it is safe
Techniquesused in ~80% of apps
Take the best-looking option now and never reconsider. Sometimes that is provably optimal and takes four lines. Sometimes it quietly loses and you never find out. The technique is easy, and knowing which case you are in is the entire skill.
Core idea. A greedy algorithm is only correct if you can argue that the locally best choice never closes off a better future. That argument is the algorithm. Without it you have a guess that happens to pass your own examples.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
greedy with a proof: take whichever finishes first
job 0
1–4
job 1
3–5
job 2
0–6
job 3
5–7
job 4
3–9
job 5
5–9
job 6
6–10
job 7
8–11
taken
nothing yet
sort by FINISHING time. The one that frees you up soonest is always at least as good as any other first choice
step 1 of 10
Sorting by finishing time works because the earliest finisher leaves the most room behind it. That sentence is the proof, and greedy without one is a guess.
↑ play a little first, then dig in