Probleme Greedy cu sortare

De ce contează?

Ai o singură sală și mai multe evenimente, fiecare cu ora de început și de sfârșit. Vrei să programezi cât mai multe fără suprapuneri. Trucul: alegi mereu evenimentul care se termină cel mai devreme — așa rămâne maximum de timp liber pentru următoarele.

Tiparul: sortează, apoi alege lacom

Multe probleme Greedy devin corecte doar dacă procesezi elementele într-o ordine potrivită. Sortarea creează acea ordine; apoi alegerea locală optimă duce la rezultatul global. E combinația dintre temele anterioare: struct + sortare + Greedy.

Problema clasică: selecția activităților

Ai n activități, fiecare cu (start, sfarsit). Vrei numărul maxim de activități care nu se suprapun. Strategia: sortezi după sfârșit crescător și iei fiecare activitate care începe după ce s-a terminat ultima aleasă.

Algoritm pas cu pas

Activități (start, sfârșit): (1,3), (2,5), (4,7), (6,8). Sortate după sfârșit: la fel.

activitate	start	sfârșit	ultima terminare	iei?
(1,3)	1	3	−	DA → ultima=3
(2,5)	2	5	3	start 2 < 3 → NU
(4,7)	4	7	3	start 4 ≥ 3 → DA → ultima=7
(6,8)	6	8	7	start 6 < 7 → NU

Rezultat: 2 activități — (1,3) și (4,7).

Implementare C++

#include <iostream>
#include <algorithm>
using namespace std;

struct Activitate {
    int start, sfarsit;
};

bool dupaSfarsit(const Activitate& a, const Activitate& b) {
    return a.sfarsit < b.sfarsit;       // sortam dupa sfarsit, crescator
}

int main() {
    int n;
    cin >> n;
    Activitate v[1000];
    for (int i = 0; i < n; i++) cin >> v[i].start >> v[i].sfarsit;

    sort(v, v + n, dupaSfarsit);

    int alese = 0, ultimaTerminare = -1;
    for (int i = 0; i < n; i++) {
        if (v[i].start >= ultimaTerminare) {    // nu se suprapune
            alese++;
            ultimaTerminare = v[i].sfarsit;     // actualizam
        }
    }
    cout << alese << "\n";      // 2
    return 0;
}

Observația-cheie

De ce sortăm după sfârșit, nu după început? Alegând activitatea care se termină cel mai devreme, eliberezi sala cât mai repede și lași loc pentru cât mai multe altele. Sortarea după început sau după durată nu dă mereu optimul.

De ce funcționează (intuitiv)

Activitatea care se termină prima nu poate strica nimic: orice soluție optimă fie o conține, fie o poate înlocui pe prima ei activitate cu aceasta, fără pierdere. Deci o putem alege mereu „cu inima împăcată" — un argument de tip „schimb" (vezi lecția-punte).

Complexitate

Etapă	Timp	Spațiu
sortare	O(n log n)	O(log n)
alegere lacomă	O(n)	O(1)
total	O(n log n)	—

Greșeli frecvente

Capcane reale la Greedy cu sortare:

Sortezi după criteriul greșit: după început sau durată în loc de sfârșit → ratezi optimul. La selecția activităților, criteriul e sfârșitul.
Comparație de suprapunere greșită: start >= ultimaTerminare (sau >, după cum definești „se atinge"). Fii consecvent cu enunțul.
Uiți să actualizezi ultimaTerminare: după ce alegi o activitate, trebuie să reții noul sfârșit, altfel compari mereu cu primul.
Presupui Greedy fără justificare: pe alte probleme cu intervale, alt criteriu (sau altă metodă) poate fi necesar. Verifică.

Vizualizare

Urmărește cum intervalele se sortează după sfârșit și cum alegerea lacomă selectează un set maxim fără suprapuneri:

Indiciu

Observă că de fiecare dată alegi intervalul care se termină cel mai devreme dintre cele încă disponibile — și cum asta lasă loc pentru cât mai multe altele.

De reținut

Multe probleme Greedy = sortează după criteriul potrivit, apoi alege lacom în acea ordine.
Selecția activităților: sortează după sfârșit, ia fiecare activitate care nu se suprapune.
O(n log n) (sortarea domină); justifică alegerea criteriului, nu o presupune.