De ce contează?
Ai o singură sală și o grămadă de evenimente care vor s-o folosească, fiecare cu ora lui de început și de sfârșit. Vrei să încapă cât mai multe fără să se suprapună. Instinctul îți șoptește: „alege mereu evenimentul care se termină cel mai devreme”. Sună rezonabil — dar de unde știi că nu există o altă alegere care ar fi încăput mai multe? În lecția asta înveți să transformi acel „pare logic” într-un argument în care chiar poți avea încredere.
Ideea-cheie
Un algoritm greedy ia, la fiecare pas, alegerea care arată cel mai bine acum, fără să se mai răzgândească. Problema e simplă de pus, dar capcana e mare: o alegere bună local poate distruge optimul global. Greedy nu este o tehnică care „merge mereu” — este o tehnică care merge doar când poți demonstra că alegerea locală nu strică niciodată soluția cea mai bună.
Vom folosi tot timpul același exemplu, selecția de intervale: avem activități
cu interval [start, sfarsit) și vrem numărul maxim de activități care nu se
suprapun. Regula greedy candidat: sortează după sfârșit și ia mereu activitatea
care se termină cel mai devreme dintre cele compatibile.
Un greedy este corect doar dacă poți argumenta că alegerea locală nu strică optimul global. Fără un astfel de argument (sau fără un contraexemplu care să-l respingă), nu ai un algoritm — ai doar o ghicire care s-a întâmplat să meargă pe exemplele pe care le-ai încercat.