Reuniunea intervalelor prin sortare în C++

Intervalele [1,4] și [3,6] acoperă împreună [1,6]. Dacă mai adăugăm [8,9], rămân două bucăți separate. Reuniunea conține toate punctele care apar în cel puțin unul dintre intervale; o reprezentăm prin cât mai puține intervale fără goluri în interiorul lor.

Capetele fac parte din interval

Citim 1≤n≤1000, apoi n perechi de întregi st,dr, cu -10^9≤st≤dr≤10^9. Intervalele sunt închise: includ ambele capete. Afișăm fiecare interval al reuniunii pe o linie, în ordine crescătoare. [1,3] și [3,5] se unesc deoarece au punctul 3 comun. [1,3] și [4,5] rămân separate: lucrăm cu intervale pe axa reală, nu doar cu mulțimi de întregi.

De ce sortăm după început

După sortare, niciun interval viitor nu începe mai la stânga decât cel curent. Păstrăm st și dr pentru bucata aflată în construcție. Dacă următorul început este cel mult dr, lărgim numai capătul drept. Folosim maximul, deoarece un interval inclus, precum [2,3] în [1,7], nu trebuie să micșoreze bucata.

Dacă următorul început depășește dr, am găsit un gol. Niciun interval ulterior nu îl poate acoperi dinspre stânga, deci afișăm bucata terminată și începem una nouă. La final trebuie afișată și ultima bucată, care nu întâlnește un gol ulterior.

Intervalele închise [1,4] și [3,6] se suprapun și formează [1,6]. Intervalul [8,9] rămâne separat.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <algorithm>
using namespace std;
struct Interval { int st,dr; };
int main() {
    int n; cin >> n;
    Interval a[1000];
    for(int i=0;i<n;++i) cin >> a[i].st >> a[i].dr;
    sort(a,a+n,[](const Interval& x,const Interval& y){return x.st<y.st;});
    int st=a[0].st,dr=a[0].dr;
    for(int i=1;i<n;++i) {
        if(a[i].st<=dr) dr=max(dr,a[i].dr);
        else { cout << st << ' ' << dr << '\n'; st=a[i].st; dr=a[i].dr; }
    }
    cout << st << ' ' << dr << '\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;
struct Interval { int st,dr; };
int main() {
    int n; cin >> n;
    vector<Interval> a(n);
    for(int i=0;i<n;++i) cin >> a[i].st >> a[i].dr;
    sort(a.begin(),a.end(),[](const Interval& x,const Interval& y){return x.st<y.st;});
    int st=a[0].st,dr=a[0].dr;
    for(int i=1;i<n;++i) {
        if(a[i].st<=dr) dr=max(dr,a[i].dr);
        else { cout << st << ' ' << dr << '\n'; st=a[i].st; dr=a[i].dr; }
    }
    cout << st << ' ' << dr << '\n';
}

Urmărește un interval inclus

Pentru intrarea [8,9], [2,3], [1,7], [6,8], sortarea dă [1,7], [2,3], [6,8], [8,9]. Capătul drept evoluează 7,7,8,9. Rezultatul este [1,9]. O atribuire simplă dr=a[i].dr ar micșora capătul la 3 și ar produce un gol fals.

Structura Interval grupează cele două capete. Comparatorul funcției sort răspunde strict dacă primul început este mai mic; nu folosim <=. Tabloul rezervă loc pentru 1000 de intervale, iar n precizează câte folosim, cu indici de la 0.

Sortarea costă O(n log n), iar parcurgerea O(n). Starea parcurgerii este constantă, dar datele ocupă O(n) memorie. Nu confunda această problemă cu selectarea intervalelor compatibile: acolo alegi unele intervale, aici păstrezi toate punctele acoperite.

Exersează

[1,4], [3,6], [8,9] produc [1,6] și [8,9]. Două copii ale lui [2,2] produc o singură bucată [2,2]. Verifică un singur interval, intervale complet incluse și o intrare dată în ordine inversă.

Continuă cu sortarea, structurile și selectarea intervalelor.

Întrebări frecvente

Cum reunesc intervalele care se suprapun?

Sortează intervalele după capătul stâng și păstrează intervalul curent. Dacă următorul începe înainte de finalul curent sau chiar în el, extinde finalul la maximul celor două capete drepte.

Se unesc intervalele închise care se ating într-un capăt?

Da. De exemplu, [1,3] și [3,5] au punctul 3 comun și formează [1,5]. Convenția capetelor trebuie precizată înainte de alegerea comparației.

De ce [1,3] și [4,5] rămân separate în lecție?

Sunt intervale pe axa reală: între 3 și 4 există puncte neacoperite. O problemă despre mulțimi de întregi consecutive ar putea folosi o altă regulă de compactare.