Algoritmi → Napredne tehnike → Metoda događaja (sweep line)

Metoda događaja (sweep line)

Najviše istovremenih intervala

U muzeju je bilo n posetilaca; za svakog znamo vreme dolaska a i odlaska b. Koliko je najviše ljudi bilo istovremeno? Svaki posetilac daje dva događaja: (a, +1) i (b, −1). Sortiramo događaje po vremenu i prolazimo, menjajući brojač.

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> dog;                // (vreme, promena)
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        dog.push_back({a, +1});                // dolazak
        dog.push_back({b, -1});                // odlazak
    }
    sort(dog.begin(), dog.end());              // kod istog vremena -1 ide pre +1
    int trenutno = 0, naj = 0;
    for (auto &d : dog) {
        trenutno += d.second;
        naj = max(naj, trenutno);
    }
    cout << naj << endl;
    return 0;
}

Parovi se sortiraju po vremenu, a kod jednakog vremena po drugoj vrednosti: −1 pre +1. To znači da posetilac koji odlazi u trenutku 4 i onaj koji dolazi u trenutku 4 nisu istovremeno u muzeju. Ako se po postavci računaju kao istovremeni, odlazak se kodira sa vremenom b + 1 ili se menja redosled.

Ukupna pokrivena dužina

Na pravoj je nacrtano n duži [a, b]. Kolika je ukupna dužina koju pokriva bar jedna duž? Pri prolasku pamtimo koliko duži trenutno pokriva liniju; deo između dva uzastopna događaja ubrajamo ako je brojač veći od 0.

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

int main() {
    int n;
    cin >> n;
    vector<pair<long long, int>> dog;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        dog.push_back({a, +1});
        dog.push_back({b, -1});
    }
    sort(dog.begin(), dog.end());
    long long ukupno = 0;
    int aktivnih = 0;
    for (size_t i = 0; i < dog.size(); i++) {
        if (i > 0 && aktivnih > 0) ukupno += dog[i].first - dog[i - 1].first;   // deo od prethodnog događaja
        aktivnih += dog[i].second;
    }
    cout << ukupno << endl;
    return 0;
}

Duži [1, 4] i [2, 6] zajedno pokrivaju [1, 6] (dužina 5), a [8, 10] još 2 – ukupno 7. Isti rezultat daje i spajanje intervala.

Veza sa nizom razlika

Kada su vremena mali celi brojevi (do 10⁶), umesto sortiranja događaja može se koristiti niz razlika: d[a]++, d[b]--, pa prefiksna suma daje broj aktivnih intervala u svakoj tački. Metoda događaja radi i kada su vremena velika (do 10⁹) ili realna – zato je opštija.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje