Numărul minim de săli pentru intervale, în C++

Avem activități cu intervale fixe și vrem să le găzduim pe toate, fără ca două activități simultane să folosească aceeași sală. Numărul minim de săli este numărul maxim de activități active în același moment.

Ce se întâmplă la aceeași oră

Citim 0≤n≤1000 și n intervale [început,sfârșit), cu 0≤început<sfârșit≤10^9. Capătul stâng este inclus, cel drept exclus. O activitate care se termină la 11 poate fi urmată în aceeași sală de una care începe la 11. Afișăm numărul minim de săli, fără repartizarea efectivă a activităților.

Intervalele [9,11), [10,12) și [11,13) cer două săli. Între 10 și 11 sunt active primele două. La 11, prima eliberează sala înainte să înceapă a treia, astfel încât nu avem nevoie de trei săli.

Numărăm începuturile și sfârșiturile în ordine

Sortăm separat toate începuturile și toate sfârșiturile. Pentru fiecare început, eliminăm întâi din numărul activ toate activitățile al căror sfârșit este cel mult acel început. Apoi adăugăm noua activitate și actualizăm maximul.

Nu mai păstrăm perechile după citire deoarece cerem numai numărul simultan de activități, nu identitatea lor. Condiția început<sfârșit garantează că un sfârșit întâlnit înaintea unui început curent aparține unei activități deja începute.

Activitățile [9,11), [10,12), [11,13) au simultan cel mult două activități. La 11, prima se termină înainte să înceapă a treia.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n; cin >> n; int inceput[1000],sfarsit[1000];
    for(int i=0;i<n;++i) cin >> inceput[i] >> sfarsit[i];
    sort(inceput,inceput+n); sort(sfarsit,sfarsit+n);
    int e=0,active=0,maxim=0;
    for(int i=0;i<n;++i) {
        while(e<n && sfarsit[e]<=inceput[i]) { --active; ++e; }
        ++active; maxim=max(maxim,active);
    }
    cout << maxim << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n; cin >> n; vector<int> inceput(n),sfarsit(n);
    for(int i=0;i<n;++i) cin >> inceput[i] >> sfarsit[i];
    sort(inceput.begin(),inceput.end()); sort(sfarsit.begin(),sfarsit.end());
    int e=0,active=0,maxim=0;
    for(int i=0;i<n;++i) {
        while(e<n && sfarsit[e]<=inceput[i]) { --active; ++e; }
        ++active; maxim=max(maxim,active);
    }
    cout << maxim << '\n';
}

De ce maximul este și necesar, și suficient

Dacă la un moment dat sunt active k activități, sunt necesare cel puțin k săli. Nu putem pune două dintre ele în aceeași sală. În sens invers, la fiecare început putem reutiliza orice sală eliberată; una nouă este necesară numai când toate cele existente sunt ocupate. Numărul maxim simultan este astfel suficient.

Indicatorul e avansează prin sfârșiturile sortate și nu revine. Deși există o buclă în interiorul alteia, toate eliminările însumează cel mult n pași. Sortarea domină timpul total, O(n log(n+1)), iar memoria pentru capete este O(n).

Tablourile clasice rezervă 1000 de poziții și folosesc indicii 0..n-1. Varianta vector construiește n elemente. Pentru n=0, bucla nu începe și răspunsul este 0. Nu accesăm primul element fără să știm că există.

Exersează

[1,2) și [2,3) cer o sală. Două copii ale lui [1,3) cer două săli. Trei intervale cu același început cer trei săli, dacă toate au durată pozitivă. Schimbă apoi convenția la capete închise și explică de ce regula pentru egalitate trebuie revizuită.

Continuă cu selectarea intervalelor compatibile, sortarea și complexitatea.

Întrebări frecvente

Cum aflu numărul minim de săli pentru activități?

Calculează numărul maxim de activități simultane. Acesta este atât o limită necesară, cât și numărul suficient de săli pentru intervalele fixe din problemă.

Pot folosi aceeași sală dacă o activitate se termină când începe alta?

Da pentru intervalele semideschise din lecție: sfârșitul este exclus. La același moment, eliberările trebuie tratate înaintea noilor începuturi.

Ce rezultat are o listă fără activități?

Zero săli. Nu există niciun interval activ, deci maximul simultaneității este zero. Inițializarea nu trebuie să presupună existența primei activități.