Greedy: Activity Selection (planificare)

Una dintre cele mai elegante și mai citate probleme de greedy. Apare sub multe nume: „planificare interviuri”, „rezervare săli”, „programare conferințe”, „scheduling de activități”.

Enunțul

Avem N activități. Activitatea i începe la momentul start[i] și se termină la end[i]. O sală/persoană poate executa o singură activitate la un moment dat (nu se suprapun).

Care e numărul maxim de activități pe care le putem programa?

Exemplu

Activități:
A: [1, 4]
B: [3, 5]
C: [0, 6]
D: [5, 7]
E: [3, 9]
F: [5, 9]
G: [6, 10]
H: [8, 11]
I: [8, 12]
J: [2, 14]
K: [12, 16]

Selecție optimă: A, D, H, K → 4 activități.

Ideea greedy

Sortează după end[i] (timpul de sfârșit). Apoi parcurge și ia fiecare activitate a cărei start ≥ end al ultimei alese.

sortează activitățile crescător după end
ultimEnd = -∞
pentru fiecare activitate (s, e):
    dacă s ≥ ultimEnd:
        adaugă activitatea în soluție
        ultimEnd = e

Intuiția

Aleg activitatea care se termină cel mai devreme - îmi lasă maximul de timp pentru restul. E ca într-o coadă de așteptare: dacă cineva intră repede și iese repede, fac loc pentru cât mai mulți după.

De ce funcționează (exchange argument)

Teoremă: alegerea cu cel mai mic end face parte din cel puțin o soluție optimă.

Dem (schiță): fie OPT = {a₁, a₂, ..., aₖ} o soluție optimă sortată după start. Dacă prima activitate aleasă, a₁, NU e cea cu cel mai mic end, fie g aceea (greedy). Atunci:

g.end ≤ a₁.end (g e ales să aibă end minim).
Înlocuim a₁ cu g în OPT → noul set are tot k activități, valid (pentru că g.end ≤ a₁.end ≤ a₂.start).
Repetăm pentru fiecare poziție.

La sfârșit, OPT devine identică cu greedy → greedy e tot optim. ∎

Capcana de evitat: sortarea după `start`

De ce nu sortăm după start?

Pentru că o activitate cu start mic dar end mare ne blochează multe alte activități. Exemplu:

A: [0, 100]   ← start mic, dar ocupă tot
B: [1, 5]
C: [6, 10]
D: [11, 15]

Sortare după start → alegem A (1 activitate).
Sortare după end → alegem B, C, D (3 activități). ✓

Sortarea după end prioritizează activitățile „rapide”, lăsând loc.

Pas cu pas

Activități:

A: [1, 4],  B: [3, 5],  C: [0, 6],  D: [5, 7],  E: [3, 9],
F: [5, 9],  G: [6, 10], H: [8, 11], I: [8, 12], J: [2, 14], K: [12, 16]

Sortare după end: A(1,4), B(3,5), C(0,6), D(5,7), E(3,9), F(5,9), G(6,10), H(8,11), I(8,12), J(2,14), K(12,16).

Parcurgere:

Pas	Activitate	Cond. (start ≥ ultimEnd)	Aleasă?	ultimEnd
0	-	start	-	-∞
1	A(1, 4)	1 ≥ -∞ ✓	DA	4
2	B(3, 5)	3 ≥ 4 ✗	NU	4
3	C(0, 6)	0 ≥ 4 ✗	NU	4
4	D(5, 7)	5 ≥ 4 ✓	DA	7
5	E(3, 9)	3 ≥ 7 ✗	NU	7
6	F(5, 9)	5 ≥ 7 ✗	NU	7
7	G(6, 10)	6 ≥ 7 ✗	NU	7
8	H(8, 11)	8 ≥ 7 ✓	DA	11
9	I(8, 12)	8 ≥ 11 ✗	NU	11
10	J(2, 14)	2 ≥ 11 ✗	NU	11
11	K(12, 16)	12 ≥ 11 ✓	DA	16

Rezultat: {A, D, H, K} → 4 activități ✓.

Cod

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int NMAX = 100005;

struct Activitate {
    int start, end;
};

Activitate v[NMAX];
int n;

bool cmp(Activitate a, Activitate b) {
    return a.end < b.end;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i].start >> v[i].end;
    }

    sort(v + 1, v + n + 1, cmp);

    int cnt = 0;
    int ultimEnd = -1;
    for (int i = 1; i <= n; i++) {
        if (v[i].start >= ultimEnd) {
            cnt = cnt + 1;
            ultimEnd = v[i].end;
        }
    }
    fout << cnt;
    return 0;
}

Complexitate: O(N log N) - sortarea domină.

Variantă: și să afișăm activitățile alese

int alese[NMAX]; // indecșii după sortare
int nrAlese = 0;

sort(v + 1, v + n + 1, cmp);

int ultimEnd = -1;
for (int i = 1; i <= n; i++) {
    if (v[i].start >= ultimEnd) {
        nrAlese = nrAlese + 1;
        alese[nrAlese] = i;
        ultimEnd = v[i].end;
    }
}

fout << nrAlese << "\n";
for (int k = 1; k <= nrAlese; k++) {
    int i = alese[k];
    fout << v[i].start << " " << v[i].end << "\n";
}

Dacă vrei indecșii din input-ul original, trebuie să păstrezi și id-ul:

struct Activitate { int start, end, id; };
// la citire:
for (int i = 1; i <= n; i++) {
    fin >> v[i].start >> v[i].end;
    v[i].id = i;
}

Variantă: deschis vs închis la capete

Atenție la enunț: dacă o activitate e [s, e) (deschis la dreapta), atunci start ≥ ultimEnd e corect.
Dacă e [s, e] (închis la dreapta), atunci două activități pot atinge: [1, 5] și [5, 8] se suprapun la momentul 5.

În acest caz, condiția devine start > ultimEnd (strict).

Exemplu:

if (v[i].start > ultimEnd) { ... } // intervale [s, e] închise
if (v[i].start >= ultimEnd) { ... } // intervale [s, e) sau [s, e] cu „atingere ok"

Probleme similare (același pattern)

1. Maximum disjoint intervals

Câte intervale dintre cele date pot fi alese astfel încât niciun perechi să nu se suprapună?

= Activity Selection. Aceeași soluție.

2. Curse de taxi

Un taxi primește N comenzi. Comanda i începe la momentul start[i] (când clientul e luat) și se termină la end[i] (când e lăsat la destinație). Taxi-ul poate executa o singură cursă la un moment dat. Câte comenzi maxim poate accepta taxi-ul?

= Activity Selection. Fiecare cursă e o „activitate”; restricția „o singură la un moment dat” e identică cu cea din enunțul original.

3. Programare săli (varianta cu O singură sală)

Aceeași problemă reformulată.

Greșeli frecvente

1. Sortare după start

Cea mai des întâlnită greșeală. Vezi capcana de mai sus. Mereu sortează după end.

2. Folosirea `<=` în loc de `<` în comparator

Pentru sortare după end, dacă două activități au același end, ordinea nu contează - soluția greedy rămâne aceeași. Dar la implementare, atenție:

bool cmp(Activitate a, Activitate b) {
    return a.end <= b.end; // GREȘIT - comparator instabil
}
sort(v + 1, v + n + 1, cmp);

C++ cere comparator strict (<, nu <=), altfel undefined behavior.

3. Confuzia tipului de interval

Interval închis [s, e] cu „atingere = suprapunere”? Cu start > ultimEnd. Interval semi-deschis [s, e)? Cu start >= ultimEnd. Citește enunțul atent.

4. Activitate cu `start > end` (input invalid)

Tratează: filtrează sau confirmă în enunț că nu apare.

5. Overflow la `ultimEnd = -∞`

Folosește un valoare clar inițială: INT_MIN, sau -1 dacă timpul e ≥ 0.

Ce să reții

Activity Selection = câte activități nesuprapuse maxim.
Greedy: sortare după end, apoi parcurgere selectând fiecare activitate compatibilă.
Complexitate: O(N log N).
Demonstrație prin exchange argument: prima activitate cu cel mai mic end e mereu o alegere bună.
Nu sortezi după start - duce la suboptim.
Atenție la convenția intervalelor: deschise ([s, e)) vs închise ([s, e]).

Probleme