De ce contează?
Ești programatorul unei singure săli de cinema. Ai o listă de filme, fiecare cu ora lui de început și de sfârșit, și vrei să rulezi cât mai multe posibil într-o zi — fără ca două să se suprapună. Pe care le alegi? Instinctul spune „pe cele mai scurte” sau „pe cele care încep primele”. Surpriza: ambele te pot duce greșit. Regula câștigătoare e mult mai simplă — alegi mereu filmul care se termină cel mai devreme, ca să eliberezi sala cât mai repede pentru următorul.
Intuiția
Fiecare film este un interval (inceput, sfarsit) pe axa timpului. Două filme se
suprapun dacă intervalele lor se intersectează. Vrei numărul maxim de intervale
care nu se ating între ele.
Gândește-te la spațiu: de fiecare dată când alegi un film, „consumi” o bucată din axă. Ca să-ți rămână cât mai mult loc pentru filmele următoare, vrei să consumi cât mai puțin — adică să alegi filmul care eliberează sala cel mai devreme. De aici vine regula: sortezi după sfârșit și iei lacom.
Cheia întregii lecții: dintre toate intervalele pe care le-ai putea alege acum, cel care se termină cel mai devreme lasă cea mai mare bucată liberă din axă pentru ce urmează. Orice altă alegere blochează cel puțin la fel de mult — deci nu poate fi mai bună. De asta alegerea lacomă „termină cel mai devreme” e sigură.