Clasa X - Ora 7: Planificarea activităților (spectacolele)

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei rezolva problema spectacolelor: un teatru are mai multe spectacole, fiecare cu ora de început și de sfârșit; vrem să alegem cât mai multe spectacole care nu se suprapun.

Sortarea spectacolelor după ora de sfârșit

Condiția de compatibilitate (regula după care se decide că două spectacole pot fi programate unul după altul)

Implementarea completă în C++

Rezolvarea problemei Spectacole

Enunțul problemei

Cerință: Avem n spectacole, fiecare cu timpul de început inceput[i] și de sfârșit sfarsit[i]. Două spectacole se pot programa unul după altul dacă nu se suprapun: începutul următorului trebuie să fie mai mare sau egal cu sfârșitul precedentului. Să se aleagă numărul maxim de spectacole compatibile.

Analogie: programul zilei

Vrei să participi la cât mai multe ateliere dintr-o zi, fără să ajungi cu întârziere. Strategia cea mai bună: alege mai întâi atelierul care se termină cel mai devreme, apoi, pe rând, primul atelier care începe după ce s-a terminat cel ales. Astfel lași cât mai mult timp liber pentru restul zilei.

Strategia greedy și pas cu pas

Strategia: sortăm spectacolele după ora de sfârșit, crescător. Alegem primul spectacol, apoi, în ordine, orice spectacol care începe după (sau exact la) sfârșitul ultimului ales.

spectacole: (1,3), (2,5), (4,6), (6,8)

sortate după sfârșit

1 alegem spectacolul (1,3); ultimul sfârșit = 3

2 (2,5): început 2 < 3, se suprapune, îl sărim

3 (4,6): început 4 ≥ 3, îl alegem; ultimul sfârșit = 6

4 (6,8): început 6 ≥ 6, îl alegem; ultimul sfârșit = 8

Observă: am ales 3 spectacole: (1,3), (4,6), (6,8). Sortarea după sfârșit este cheia: lăsăm cât mai mult loc pentru spectacolele următoare.

Programul complet în C++

Păstrăm începuturile și sfârșiturile în două tablouri paralele. Sortăm crescător după sfârșit (mutând împreună și începutul), apoi parcurgem spectacolele și numărăm.

citește n, (început[i], sfârșit[i]) pentru i = 1..n sortează spectacolele crescător după sfârșit // criteriul greedy nr = 1 ultimul = sfârșit[1] // primul spectacol este mereu ales pentru i = 2, n execută dacă început[i] >= ultimul atunci // compatibil cu ultimul ales nr = nr + 1 ultimul = sfârșit[i] sfârșit dacă sfârșit pentru scrie nr

C++ - numărul maxim de spectacole

#include <iostream>
using namespace std;

int inceput[101], sfarsit[101];

void sorteaza(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (sfarsit[i] > sfarsit[j]) {
                int aux = sfarsit[i];
                sfarsit[i] = sfarsit[j];
                sfarsit[j] = aux;
                aux = inceput[i];
                inceput[i] = inceput[j];
                inceput[j] = aux;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> inceput[i] >> sfarsit[i];
    }
    sorteaza(n);
    int nr = 1;
    int ultimul = sfarsit[1];
    for (int i = 2; i <= n; i++) {
        if (inceput[i] >= ultimul) {
            nr++;
            ultimul = sfarsit[i];
        }
    }
    cout << nr << endl;
    return 0;
}

Ce învățăm: la sortare mutăm împreună perechea (început, sfârșit); alegem întotdeauna primul spectacol, iar pe următoarele doar dacă încep după ultimul sfârșit reținut.

Exercițiu de completare

Completează descrierea strategiei pentru spectacole:

Sortăm spectacolele după ______ul lor. Alegem primul ______, apoi fiecare spectacol al cărui ______ este mai mare sau egal cu ______ul ultimului ales.

Bancă de cuvinte:

sfârșit spectacol început

Exercițiu de completare: codul

Completează descrierea programului:

Pentru sortare comparăm sfârșiturile: dacă sfarsit[i] ______ sfarsit[j], le ______ împreună cu începuturile. Numărăm spectacolele alese cu ______ nr.

Bancă de cuvinte:

> schimbăm contorul

Test de înțelegere

Test rapid - spectacolele:

1. Criteriul greedy pentru problema spectacolelor este sortarea după:

ora de sfârșit ora de început durata spectacolului

2. Două spectacole i și j (i înaintea lui j) sunt compatibile dacă:

inceput[j] ≥ sfarsit[i] inceput[j] ≤ sfarsit[i] sfarsit[j] ≥ sfarsit[i]

3. Pentru a maximiza numărul de spectacole, alegem întâi spectacolul care:

se termină cel mai devreme începe cel mai devreme durează cel mai mult

Ai grijă la: sortarea se face după ora de sfârșit, nu după ora de început și nu după durată; atunci când se schimbă sfarsit[], trebuie schimbat și inceput[] corespunzător.

Aprofundare

De ce sortarea după sfârșit, nu după început sau durată? Un spectacol care se termină devreme lasă mai mult timp liber pentru spectacolele următoare. Sortarea după început ar putea alege un spectacol lung care blochează toată ziua, iar sortarea după durată ar putea alege spectacole scurte plasate prost în timp. Criteriul „cel mai devreme sfârșit" este cel care maximizează spațiul rămas pentru alegerile viitoare, deci este optimul local corect.

Corectitudinea alegerii primului spectacol: primul spectacol din lista sortată (cel care se termină cel mai devreme) poate fi luat întotdeauna: dacă o soluție optimă începea cu alt spectacol, îl înlocuim pe acela cu primul, fără a pierde niciun spectacol următor, pentru că noul spectacol se termină mai devreme. Acest raționament de „schimb" este demonstrația clasică a corectitudinii Greedy.

Inegalitatea de compatibilitate: două spectacole sunt compatibile dacă început[i] >= sfârșit[ultimul ales]. Dacă enunțul permite suprapunere doar în punctul exact (un spectacol se termină exact când începe altul), condiția cu >= este corectă; dacă suprapunerea chiar și în punct este interzisă, se folosește >. Citește întotdeauna enunțul cu atenție.

Complexitatea: sortarea cu metoda bulelor este O(n), iar parcurgerea finală este O(n). Pentru n mare se poate folosi o sortare mai eficientă (chiar merge sort, de la ora 3), caz în care algoritmul total devine O(n log n).

Exemplu din viața reală: un organizator de conferințe are mai multe prezentări propuse și o singură sală. Strategia „alege mereu prezentarea care se termină cel mai devreme" îi garantează numărul maxim de prezentări acceptate. Aceeași problemă apare la planificarea întâlnirilor într-o agendă, la programarea filmelor într-un cinematograf sau la selectarea joburilor pe o singură mașină.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Spectacole

Enunț:

Cerință: Într-un teatru se organizează n spectacole, fiecare cu timpul de început și de sfârșit. Să se determine numărul maxim de spectacole care pot fi programate, fără suprapuneri.

Date de intrare:

Programul citește n, apoi n perechi: ora de început și ora de sfârșit.

Date de ieșire:

Programul va afișa numărul maxim de spectacole.

Restricții și precizări:

1 ≤ n ≤ 100; timpurile sunt numere naturale; două spectacole nu se suprapun dacă începutul unuia este mai mare sau egal cu sfârșitul celuilalt.

Exemplu:

Intrare:

Ieșire:

Cum gândim soluția:

Sortăm spectacolele după ora de sfârșit
Alegem primul spectacol și reținem sfârșitul lui
Pentru fiecare următor, dacă începutul ≥ ultimul sfârșit, îl alegem

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int inceput[101], sfarsit[101];

void sorteaza(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (sfarsit[i] > sfarsit[j]) {
                int aux = sfarsit[i];
                sfarsit[i] = sfarsit[j];
                sfarsit[j] = aux;
                aux = inceput[i];
                inceput[i] = inceput[j];
                inceput[j] = aux;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> inceput[i] >> sfarsit[i];
    }
    sorteaza(n);
    int nr = 1;
    int ultimul = sfarsit[1];
    for (int i = 2; i <= n; i++) {
        if (inceput[i] >= ultimul) {
            nr++;
            ultimul = sfarsit[i];
        }
    }
    cout << nr << endl;
    return 0;
}

Ce învățăm: problema se rezolvă cu metoda Greedy: sortare după sfârșit + alegerea spectacolelor compatibile.

PbInfo - Activități

Enunț:

Cerință: O persoană poate participa la mai multe activități într-o zi. Fiecare activitate are un interval [a, b]. Să se afișeze numărul maxim de activități la care poate participa, fără suprapuneri.

Date de intrare:

Programul citește n, apoi n perechi (a, b) reprezentând intervalul fiecărei activități.

Date de ieșire:

Programul va afișa numărul maxim de activități.

Restricții și precizări:

1 ≤ n ≤ 100; a < b; se folosește metoda Greedy (sortare după capătul drept al intervalului).

Exemplu:

Intrare:

Ieșire:

Cum gândim soluția:

Sortăm activitățile după capătul drept b
Alegem prima activitate
Alegem următoarele doar dacă a ≥ sfârșitul ultimei alese

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int a[101], b[101];

void sorteaza(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (b[i] > b[j]) {
                int aux = b[i];
                b[i] = b[j];
                b[j] = aux;
                aux = a[i];
                a[i] = a[j];
                a[j] = aux;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    sorteaza(n);
    int nr = 1;
    int ultimul = b[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] >= ultimul) {
            nr++;
            ultimul = b[i];
        }
    }
    cout << nr << endl;
    return 0;
}

Ce învățăm: problema Activități este identică cu Spectacole; sortarea după capătul drept garantează numărul maxim de activități compatibile.

EXERCIȚII PRACTICE

Exercițiul Practic: variante pentru spectacole

Sarcini de lucru

Rezolvă sarcinile de mai jos pentru a aprofunda problema planificării activităților

Sarcina 1: Afișează spectacolele alese

Cerință: Scrie un program care afișează nu doar numărul maxim de spectacole, ci și numerele de ordine (inițiale) ale spectacolelor alese, în ordinea programării.

Scrie programul C++ aici:

Soluție pentru Sarcina 1:

#include <iostream>
using namespace std;

int inceput[101], sfarsit[101], nrS[101];

void sorteaza(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (sfarsit[i] > sfarsit[j]) {
                int aux = sfarsit[i];
                sfarsit[i] = sfarsit[j];
                sfarsit[j] = aux;
                aux = inceput[i];
                inceput[i] = inceput[j];
                inceput[j] = aux;
                aux = nrS[i];
                nrS[i] = nrS[j];
                nrS[j] = aux;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> inceput[i] >> sfarsit[i];
        nrS[i] = i;
    }
    sorteaza(n);
    int ultimul = sfarsit[1];
    cout << nrS[1] << " ";
    for (int i = 2; i <= n; i++) {
        if (inceput[i] >= ultimul) {
            cout << nrS[i] << " ";
            ultimul = sfarsit[i];
        }
    }
    return 0;
}

Verifică: pentru spectacolele (1,3), (2,5), (4,6), (6,8), afișăm 1 3 4 (numerele inițiale). La sortare mutăm împreună și numărul de ordine nrS.

Sarcina 2: Spectacole cu ore și minute

Cerință: Orele de început și de sfârșit se dau ca oră și minut (h1 m1 h2 m2). Convertește-le în minute și calculează numărul maxim de spectacole compatibile.

Scrie programul C++ aici:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

int inceput[101], sfarsit[101];

void sorteaza(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (sfarsit[i] > sfarsit[j]) {
                int aux = sfarsit[i];
                sfarsit[i] = sfarsit[j];
                sfarsit[j] = aux;
                aux = inceput[i];
                inceput[i] = inceput[j];
                inceput[j] = aux;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    int h1, m1, h2, m2;
    for (int i = 1; i <= n; i++) {
        cin >> h1 >> m1 >> h2 >> m2;
        inceput[i] = h1 * 60 + m1;
        sfarsit[i] = h2 * 60 + m2;
    }
    sorteaza(n);
    int nr = 1;
    int ultimul = sfarsit[1];
    for (int i = 2; i <= n; i++) {
        if (inceput[i] >= ultimul) {
            nr++;
            ultimul = sfarsit[i];
        }
    }
    cout << nr << endl;
    return 0;
}

Verifică: transformăm fiecare moment în minute de la miezul nopții (h * 60 + m) și aplicăm același algoritm greedy ca la problema Spectacole.

SCRIE PE CAIET

Scrie pe caiet - Planificarea activităților (spectacolele)

Titlul lecției

Ora 7: Planificarea activităților (spectacolele)

Definiția lecției

Problema cere alegerea numărului maxim de spectacole compatibile dintr-o listă de n spectacole cu intervale [început, sfârșit]. Două spectacole sunt compatibile dacă începutul următorului este mai mare sau egal cu sfârșitul precedentului. Criteriul greedy este sortarea crescătoare a spectacolelor după ora de sfârșit: un spectacol care se termină devreme lasă maximum de timp liber pentru restul. Apoi se alege primul spectacol din lista sortată și, pe rând, fiecare spectacol compatibil cu ultimul ales, numărându-se totalul. Corectitudinea se demonstrează prin argumentul de schimb: primul spectacol din lista sortată poate înlocui orice prim spectacol dintr-o soluție optimă, fără a reduce numărul de spectacole. Implementarea folosește două tablouri paralele (început, sfârșit), o sortare proprie cu interschimbarea perechilor și o buclă de numărare cu condiția inceput[i] >= ultimul.

Definiții esențiale

Problema spectacolelor: se dau n spectacole cu intervale [început, sfârșit]; se cere numărul maxim de spectacole mutual compatibile (care nu se suprapun), pe o singură „sală".
Compatibilitate: spectacolul i este compatibil cu ultimul spectacol ales dacă început[i] >= sfârșit[ultimul].
Criteriul greedy: sortarea spectacolelor crescător după ora de sfârșit și alegerea primului spectacol, apoi a fiecărui spectacol compatibil.
Corectitudine: un spectacol care se termină devreme lasă maximum de timp liber pentru restul; demonstrația se face prin „schimb": primul spectacol din lista sortată poate înlocui orice prim spectacol dintr-o soluție optimă.

Algoritmul cheie - pseudocod

Sortează spectacolele după sfârșit (mutând împreună și începuturile).
Alegeri: nr = 1, ultimul = sfârșit[1]; pentru i de la 2 la n, dacă început[i] >= ultimul, numără și actualizează ultimul.

Algoritmul cheie - cod C++

Tablouri paralele globale int inceput[101], sfarsit[101];
Funcția sorteaza(int n) cu două bucle și interschimbarea perechii (început, sfârșit).
În main(): citește, sortează, numără cu condiția inceput[i] >= ultimul, afișează nr.

Greșeli comune de evitat

Sortarea după început sau după durată în loc de sfârșit: soluția nu mai este optimă.
Interschimbarea doar a sfârșiturilor, fără începuturile corespunzătoare: perechile se amestecă.
Inițializarea greșită a lui nr (de la 0 pierde primul spectacol).
Folosirea lui > în loc de >= când spectacolele pot începe exact la finalul altuia.

Sfaturi practice și trucuri

Verifică pe exemplul (1,3), (2,5), (4,6), (6,8): răspunsul corect este 3.
Reține formula de compatibilitate ca pe o „regulă de aur": început[i] >= ultimulSfârșit.
La oral, justifică alegerea primului spectacol prin argumentul de schimb.
Dacă enunțul cere și lista spectacolelor alese, reține pozițiile în vector și afișează-le la final.

Exemplu practic

Un elev programează vizitele la bibliotecă într-o săptămână, fiecare vizită având un interval orar, și vrea cât mai multe vizite care nu se suprapun. Sortează intervalele după ora de încheiere și alege mereu prima vizită care începe după ce s-a terminat cea aleasă anterior, exact ca în fragmentul de mai jos (după sortarea după sfarsit):

C++ - alegerea numărului maxim de activități compatibile

int nr = 1, ultimul = sfarsit[1];
for (int i = 2; i <= n; i++) {
    if (inceput[i] >= ultimul) {
        nr++;
        ultimul = sfarsit[i];
    }
}
cout << nr << endl;

Ora 7: Planificarea activităților (spectacolele)

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Enunțul problemei

Analogie: programul zilei

Strategia greedy și pas cu pas

spectacole: (1,3), (2,5), (4,6), (6,8)

Programul complet în C++

Exercițiu de completare

Completează descrierea strategiei pentru spectacole:

Bancă de cuvinte:

Exercițiu de completare: codul

Completează descrierea programului:

Bancă de cuvinte:

Test de înțelegere

Test rapid - spectacolele:

Aprofundare

PbInfo - Spectacole

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

PbInfo - Activități

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

Exercițiul Practic: variante pentru spectacole

Sarcini de lucru

Sarcina 1: Afișează spectacolele alese

Soluție pentru Sarcina 1:

Sarcina 2: Spectacole cu ore și minute

Soluție pentru Sarcina 2:

Scrie pe caiet - Planificarea activităților (spectacolele)

Titlul lecției

Definiția lecției

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic