De ce contează?
Împarți cadouri grele la prieteni și fiecare trebuie să care un cadou un anumit număr de zile. Vrei ca efortul total (greutate × zile) să fie cât mai mic. Intuitiv: cadoul cel mai greu îl dai cuiva care îl cară cele mai puține zile, iar cel mai ușor cuiva care îl cară cele mai multe. Perechezi mare cu mic. Exact asta face greedy-ul cu sortare.
Intuiția
Multe probleme greedy au același tipar: întâi sortezi după criteriul potrivit, apoi parcurgi în ordine și alegi lacom. Greul nu e parcurgerea — e să găsești după ce sortezi și în ce ordine. Aici problema e: ai doi vectori și trebuie să-i împerechezi element cu element ca să minimizezi suma produselor. Imaginea mentală: ca să nu „dublezi" un număr mare, îl pui mereu lângă unul mic.