Metoda greedy: selectarea intervalelor în C++

Greedy construiește o soluție alegând la fiecare pas o variantă local avantajoasă. Metoda este corectă numai dacă acea alegere poate fi justificată pentru problema concretă. O intuiție despre „cel mai mic” sau „cel mai mare” nu este suficientă.

Exemplul clasic este selectarea unui număr maxim de activități care nu se suprapun, fiecare având un început și un sfârșit. Toate activitățile au aceeași valoare în obiectiv: contează câte alegem, nu durata sau profitul lor.

Cum funcționează

Ordonăm intervalele după momentul de terminare. Alegem primul interval disponibil și apoi fiecare interval care începe cel puțin la sfârșitul ultimului ales. Terminarea timpurie lasă cât mai mult loc pentru activitățile viitoare.

Convenția intervalelor este [s,f), cu s<f. Astfel, o activitate care începe exact când precedenta se termină este compatibilă. Programul presupune momente nenegative, maximum o sută de intervale și pornește end de la zero. Pentru momente negative, inițializarea ar trebui adaptată sau prima alegere tratată separat.

Alegerea intervalului cu cea mai scurtă durată nu este în general corectă: un interval scurt din mijloc poate intersecta două activități compatibile între ele. Nici alegerea celui care începe primul nu garantează un număr maxim. Regula depinde de obiectiv și de structura restricțiilor, nu de faptul că toate datele sunt intervale.

Exemplu urmărit pas cu pas

Pentru [0,3), [1,2), [2,4), [4,5), ordinea terminărilor începe cu [1,2). Îl alegem, respingem [0,3), apoi alegem [2,4) și [4,5). Rezultatul are trei activități.

Intervalul [0,3) începe mai devreme, dar ar bloca [1,2) și [2,4), reducând numărul alegerilor. Exemplul arată de ce criteriul de sortare nu poate fi schimbat fără o nouă demonstrație. La egalitate între sfârșituri, oricare dintre activitățile eligibile lasă același prag pentru viitor.

Implementare C++17

Varianta clasică:

#include <algorithm>
#include <iostream>
struct Interval {
    int s, f;
};
int main() {
    int n;
    std::cin >> n;
    Interval a[100];
    for (int i = 0; i < n; ++i)
        std::cin >> a[i].s >> a[i].f;
    std::sort(a, a + n, [](Interval x, Interval y) { return x.f < y.f; });
    int end = 0, count = 0;
    for (int i = 0; i < n; ++i)
        if (a[i].s >= end) {
            ++count;
            end = a[i].f;
        }
    std::cout << count << '\n';
}

Varianta cu std::vector:

#include <algorithm>
#include <iostream>
#include <vector>
struct Interval {
    int s, f;
};
int main() {
    int n;
    std::cin >> n;
    std::vector<Interval> a(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i].s >> a[i].f;
    std::sort(a.begin(), a.end(), [](Interval x, Interval y) { return x.f < y.f; });
    int end = 0, count = 0;
    for (int i = 0; i < n; ++i)
        if (a[i].s >= end) {
            ++count;
            end = a[i].f;
        }
    std::cout << count << '\n';
}

De ce funcționează și cât costă

Consideră o soluție optimă și primul ei interval. Intervalul greedy se termină cel târziu odată cu acesta. Îl putem înlocui fără să stricăm compatibilitatea activităților următoare. După această alegere sigură, argumentul se repetă pentru intervalele rămase: acesta este un argument de schimb.

Sortarea costă O(n log n), iar selecția O(n). Memoria depinde de stocarea intervalelor și implementarea sortării. Dacă intervalele sunt deja sortate corect, faza de selecție este liniară.

Greșeli frecvente

Nu aplica automat algoritmul când fiecare activitate are profit diferit: maximizarea profitului este o altă problemă, rezolvată de obicei prin programare dinamică. Nu folosi un comparator cu <= în std::sort.

Exersează

Construiește trei intervale care arată că alegerea activității cu începutul minim nu este întotdeauna optimă.

Rezolvare explicată: Intervalele [0,10), [1,2), [2,3) sunt suficiente. Alegerea primei activități dă una, iar ultimele două sunt compatibile și dau două.

Continuă să înveți

Sortare, complexitate și programare dinamică.

Întrebări frecvente

De unde știu că o alegere greedy este corectă?

Ai nevoie de o justificare, de exemplu un argument de schimb sau un invariant. Testele găsesc contraexemple, dar nu înlocuiesc demonstrația pentru toate intrările.

De ce sortăm după sfârșit?

Intervalul care se termină cel mai devreme lasă disponibil un interval de timp cel puțin la fel de mare pentru alegerile ulterioare.

Pot alege două activități care se ating?

În convenția [s,f) folosită aici, da. Dacă enunțul cere o pauză sau folosește altă regulă, condiția de compatibilitate trebuie schimbată.

Funcționează și pentru profituri diferite?

Nu în general. Un interval lung și foarte profitabil poate fi preferabil mai multor intervale scurte. Obiectivul cere altă analiză și alt algoritm.

Greedy încearcă toate variantele?

Nu. Face alegeri definitive conform regulii sale. Această economie explică viteza, dar și necesitatea de a demonstra că alegerile nu pierd optimul.