Bun venit, pasionatule de programare și algoritmi! 👋 Astăzi ne scufundăm într-o problemă clasică, dar incredibil de utilă în lumea informaticii: Merge Intervals Problem. Este o provocare frecvent întâlnită în interviurile tehnice și are nenumărate aplicații în scenarii din viața reală. Nu este doar un exercițiu de gândire, ci o abilitate esențială pe care merită să o stăpânești. În acest articol, vom explora această enigmă algoritmică în detaliu, oferind o abordare pas-cu-pas și o implementare clară, optimizată în C++. Pregătește-te să-ți cizelezi logica și să adaugi o unealtă valoroasă în arsenalul tău de programator!
### Înțelegerea Profundă a Problemei Merge Intervals 🧐
Să începem prin a desluși exact ce presupune această problemă. Ni se oferă o colecție de intervale, unde fiecare interval este reprezentat de o pereche de numere `[start, end]`. Scopul nostru este să fuzionăm toate intervalele care se suprapun și să returnăm o nouă colecție de intervale, în care niciunul nu se suprapune.
De exemplu:
Dacă avem intervalele `[[1,3],[2,6],[8,10],[15,18]]`:
* `[1,3]` și `[2,6]` se suprapun, deoarece 2 se află între 1 și 3. Le putem contopi în `[1,6]`.
* Apoi, `[8,10]` și `[15,18]` nu se suprapun cu `[1,6]` și nici între ele.
Rezultatul final ar fi `[[1,6],[8,10],[15,18]]`.
Pare simplu, nu-i așa? Dar complexitatea apare atunci când trebuie să gestionăm o listă extinsă de segmente, cu multiple suprapuneri sau cazuri limită. O abordare naivă, care ar verifica fiecare interval cu fiecare alt interval, ar fi ineficientă. Avem nevoie de o metodă mai rafinată și structurată.
### De Ce Este Crucial Să Înțelegem Această Problemă? Aplicații Reale 🌍
Poate te întrebi de ce este atât de importantă o astfel de provocare algoritmică. Ei bine, abilitatea de a gestiona și a contopi intervale are un spectru larg de aplicații practice în diverse domenii:
1. **Managementul Calendarelor și Orarului**: Imaginează-ți o aplicație de calendar care trebuie să afișeze evenimentele tale. Dacă ai două întâlniri programate `[9:00, 10:00]` și `[9:30, 10:30]`, sistemul ar putea fuziona vizual aceste segmente pentru a indica o perioadă ocupată continuă de la `[9:00, 10:30]`. Similar, în planificarea resurselor, se pot contopi blocuri de timp pentru a optimiza alocările.
2. **Analiza Datelor Geospațiale**: În sistemele GIS, suprafețele geografice pot fi reprezentate ca intervale (sau, mai complex, poligoane). Fuzionarea lor poate indica zone de interes comune sau extinderea anumitor fenomene.
3. **Procesarea Datelor Genomice**: În bioinformatică, secvențele de ADN sau zonele genetice pot fi reprezentate ca intervale. Fuzionarea lor ajută la identificarea regiunilor comune sau la analiza structurii genomului.
4. **Alocarea Resurselor**: Într-un sistem de operare, alocarea memoriei sau a procesorului se face adesea în blocuri. Fuzionarea intervalelor de memorie libere poate crea spații contigue mai mari, mai ușor de gestionat.
5. **Programare Concurrentă**: Uneori, trebuie să gestionăm intervale de blocare sau acces la resurse partajate, iar contopirea lor poate simplifica logica de sincronizare.
În esență, oriunde există segmente, perioade de timp sau plaje de valori care pot interacționa sau se pot suprapune, algoritmul de fuzionare a intervalelor își găsește utilitatea.
### Abordarea Algoritmică: Cheia Rezolvării 💡
Secretul unei soluții eficiente stă într-un pas fundamental: sortarea. Fără o colecție ordonată, verificarea suprapunerilor devine un coșmar.
#### Pasul 1: Sortarea Intervalelor ⬆️
Primul și cel mai important pas este să sortăm toate intervalele pe baza valorii lor de început (`start`). Dacă două intervale au aceeași valoare de început, le putem sorta pe baza valorii de sfârșit (`end`), deși acest lucru este opțional în majoritatea cazurilor pentru corectitudine, dar poate optimiza puțin.
De ce este crucială sortarea? Imaginează-ți că ai intervalele `[[6,8],[1,3],[2,4]]`. Fără sortare, ar trebui să verifici `[6,8]` cu `[1,3]`, apoi `[2,4]`, etc. După sortare, lista devine `[[1,3],[2,4],[6,8]]`. Acum, știm că, dacă un interval `[a,b]` nu se suprapune cu `[c,d]` și `a < c`, atunci `[a,b]` nu se va suprapune niciodată cu niciun interval care începe *după* `c` (presupunând că `b < c`). Această proprietate ne permite să iterăm liniar prin lista sortată, verificând suprapunerea doar cu ultimul interval fuzionat. #### Pasul 2: Iterarea și Fuzionarea 🔄 După ce lista de intervale este sortată, putem începe procesul de fuzionare. Vom folosi o listă nouă pentru a stoca rezultatul final.
1. **Inițializare**: Dacă lista de intervale inițiale este goală, returnăm o listă goală. Altfel, adăugăm primul interval sortat în lista noastră de rezultate. Acesta va fi primul nostru interval "fuzionat" provizoriu. 2. **Parcurgere**: Iterăm prin restul intervalelor, începând cu al doilea. Pentru fiecare interval curent (`currentInterval`): * **Verificăm suprapunerea**: Comparăm `currentInterval` cu ultimul interval adăugat în lista de rezultate (`lastMergedInterval`). * **Condiția de suprapunere**: Două intervale `[a,b]` și `[c,d]` se suprapun dacă `b >= c`. (Aici presupunem că `a <= c` datorită sortării). * **Dacă există suprapunere**: Asta înseamnă că `currentInterval.start` este mai mic sau egal cu `lastMergedInterval.end`. În acest caz, trebuie să fuzionăm aceste două intervale. Cum facem asta? Simplu: actualizăm `lastMergedInterval.end` pentru a fi maximul dintre `lastMergedInterval.end` și `currentInterval.end`. Practic, extindem intervalul fuzionat. * **Dacă nu există suprapunere**: Asta înseamnă că `currentInterval.start` este mai mare decât `lastMergedInterval.end`. Nu le putem fuziona. Prin urmare, adăugăm `currentInterval` la lista noastră de rezultate, iar acesta devine noul `lastMergedInterval` pentru comparațiile ulterioare. Să reluăm exemplul nostru `[[1,3],[2,6],[8,10],[15,18]]` și să aplicăm pașii: 1. **Sortare**: Lista este deja sortată după valorile de start. 2. **Inițializare**: Lista de rezultate `res` este `[[1,3]]`. `lastMergedInterval` este `[1,3]`. 3. **Iterare**: * **Interval curent `[2,6]`**: * Se suprapune cu `lastMergedInterval [1,3]`? Da, `3 >= 2`.* Fuzionăm: `lastMergedInterval` devine `[1, max(3,6)]` adică `[1,6]`.
* `res` este acum `[[1,6]]`.
* **Interval curent `[8,10]`**:
* Se suprapune cu `lastMergedInterval [1,6]`? Nu, `6 < 8`. * Nu fuzionăm. Adăugăm `[8,10]` la `res`. * `res` este acum `[[1,6],[8,10]]`. `lastMergedInterval` devine `[8,10]`. * **Interval curent `[15,18]`**: * Se suprapune cu `lastMergedInterval [8,10]`? Nu, `10 < 15`. * Nu fuzionăm. Adăugăm `[15,18]` la `res`. * `res` este acum `[[1,6],[8,10],[15,18]]`. `lastMergedInterval` devine `[15,18]`. 4. **Final**: Am parcurs toate intervalele. Lista `res` este soluția finală. Această abordare este elegantă și eficientă! ### Implementare în C++: Cod Clar și Eficient 💻 Acum că am înțeles logica, să o transpunem în cod C++. Vom folosi un `std::vector
„`cpp
#include
#include
#include
class Solution {
public:
std::vector
// Pasul 1: Gestionarea cazurilor limită
// Dacă nu există intervale sau există un singur interval, nu e nimic de fuzionat.
if (intervals.empty() || intervals.size() == 1) {
return intervals;
}
// Pasul 2: Sortarea intervalelor
// Sortăm intervalele pe baza valorii de început.
// Dacă valorile de început sunt egale, sortăm după valoarea de sfârșit.
// Folosim o expresie lambda pentru comparație personalizată.
std::sort(intervals.begin(), intervals.end(), [](const std::vector
if (a[0] != b[0]) {
return a[0] < b[0]; // Sortăm după început
}
return a[1] < b[1]; // Dacă începuturile sunt egale, sortăm după sfârșit
});
// Inițializăm vectorul de rezultate
std::vector
// Adăugăm primul interval sortat în lista de rezultate.
// Acesta va fi primul interval „fuzionat” cu care vom compara.
mergedIntervals.push_back(intervals[0]);
// Pasul 3: Iterarea și Fuzionarea
// Parcurgem restul intervalelor, începând cu al doilea.
for (size_t i = 1; i < intervals.size(); ++i) {
// Obținem ultimul interval fuzionat din lista de rezultate.
// Aceasta ne permite să verificăm dacă intervalul curent se suprapune cu el.
std::vector
// Verificăm dacă intervalul curent se suprapune cu ultimul fuzionat.
// Suprapunere există dacă valoarea de început a intervalului curent
// este mai mică sau egală cu valoarea de sfârșit a ultimului interval fuzionat.
if (intervals[i][0] <= lastMerged[1]) {
// Dacă se suprapun, fuzionăm prin actualizarea valorii de sfârșit a
// ultimului interval fuzionat cu maximul dintre valoarea sa curentă de sfârșit
// și valoarea de sfârșit a intervalului curent.
lastMerged[1] = std::max(lastMerged[1], intervals[i][1]);
} else {
// Dacă nu se suprapun, intervalul curent este unul nou, ne-suprapus.
// Îl adăugăm pur și simplu la lista de rezultate.
mergedIntervals.push_back(intervals[i]);
}
}
return mergedIntervals;
}
};
// Funcție ajutătoare pentru afișarea rezultatelor
void printIntervals(const std::vector
std::cout << "[";
for (size_t i = 0; i < intervals.size(); ++i) {
std::cout << "[" << intervals[i][0] << "," << intervals[i][1] << "]";
if (i < intervals.size() - 1) {
std::cout << ",";
}
}
std::cout << "]" << std::endl;
}
int main() {
Solution sol;
// Exemplul 1
std::vector
std::cout << "Intrari: ";
printIntervals(intervals1);
std::vector
std::cout << "Iesiri: ";
printIntervals(result1); // Așteptat: [[1,6],[8,10],[15,18]]
std::cout << std::endl;
// Exemplul 2
std::vector
std::cout << "Intrari: ";
printIntervals(intervals2);
std::vector
std::cout << "Iesiri: ";
printIntervals(result2); // Așteptat: [[1,5]]
std::cout << std::endl;
// Exemplul 3
std::vector
std::cout << "Intrari: ";
printIntervals(intervals3);
std::vector
std::cout << "Iesiri: ";
printIntervals(result3); // Așteptat: [[0,4]]
std::cout << std::endl;
// Exemplul 4
std::vector
std::cout << "Intrari: ";
printIntervals(intervals4);
std::vector
std::cout << "Iesiri: ";
printIntervals(result4); // Așteptat: [[0,0],[1,4]]
std::cout << std::endl;
// Exemplul 5: Fără suprapuneri
std::vector
std::cout << "Intrari: ";
printIntervals(intervals5);
std::vector
std::cout << "Iesiri: ";
printIntervals(result5); // Așteptat: [[1,2],[3,4],[5,6]]
std::cout << std::endl;
return 0;
}
```
**Explicația Codului:**
* **`#include` directives**: Includem librăriile necesare: `iostream` pentru operații de intrare/ieșire, `vector` pentru structura de date dinamică și `algorithm` pentru funcția de sortare.
* **`merge(std::vector
* **Cazuri limită**: Verifică dacă lista de intervale este goală sau are doar un singur element. În aceste scenarii, nu este necesară nicio fuzionare, iar lista originală este returnată. Acest pas adaugă **robustete** soluției.
* **Sortare**: Utilizează `std::sort` împreună cu o funcție lambda pentru a ordona intervalele. Comparatorul lambda se asigură că sortarea se face mai întâi după punctul de start (`a[0]`) și, în cazul egalității, după punctul de sfârșit (`a[1]`). Acest lucru este fundamental pentru eficiența ulterioară.
* **`mergedIntervals`**: Un `std::vector` gol inițial, care va stoca rezultatele fuzionate.
* **Adăugarea primului interval**: Primul interval din lista sortată este adăugat direct în `mergedIntervals`. Acesta servește drept punct de plecare pentru comparații.
* **Bucla de iterație**: Se parcurge restul intervalelor (de la al doilea element).
* **`lastMerged`**: O referință la ultimul interval adăugat (și potențial fuzionat) în `mergedIntervals`. Accesarea cu `back()` și utilizarea unei referințe permite modificarea directă a acestui interval în vectorul rezultat.
* **Condiția de suprapunere**: `intervals[i][0] <= lastMerged[1]`. Această expresie verifică dacă punctul de start al intervalului curent este mai mic sau egal cu punctul de sfârșit al ultimului interval fuzionat. Dacă este adevărat, înseamnă că există o suprapunere.
* **Fuzionare**: Dacă se suprapun, punctul de sfârșit al `lastMerged` este actualizat la valoarea maximă dintre punctul său de sfârșit curent și punctul de sfârșit al `intervals[i]`. Aceasta extinde `lastMerged` pentru a include `intervals[i]`.
* **Adăugare interval nou**: Dacă nu există suprapunere, `intervals[i]` este un interval distinct și este adăugat ca atare la `mergedIntervals`.
* **`printIntervals` function**: O funcție utilitară pentru a afișa vectorii de intervale într-un format lizibil.
* **`main` function**: Conține exemple de utilizare a clasei `Solution` pentru a demonstra funcționalitatea algoritmului.
### Analiza Complexității ⏱️
Un aspect vital al oricărei soluții algoritmice este înțelegerea performanței sale.
* **Complexitate Temporală (Time Complexity)**:
* **Sortarea**: Operația de sortare a `N` intervale durează `O(N log N)`, unde `N` este numărul de intervale. Aceasta este dominanta în algoritmul nostru.
* **Iterarea și Fuzionarea**: După sortare, parcurgem lista de intervale o singură dată. Fiecare operație în buclă (verificare, fuzionare sau adăugare) se realizează în timp constant. Prin urmare, această fază are o complexitate de `O(N)`.
* **Total**: Complexitatea temporală generală a soluției este `O(N log N)`, datorită etapei de sortare.
* **Complexitate Spațială (Space Complexity)**:
* **Stocarea rezultatului**: În cel mai rău caz, dacă niciun interval nu se suprapune, lista de rezultate `mergedIntervals` va conține toate `N` intervalele originale. Prin urmare, necesită `O(N)` spațiu suplimentar.
* **Spațiu pentru sortare**: Depinde de implementarea `std::sort`. De obicei, folosește `O(log N)` sau `O(N)` spațiu auxiliar, în funcție de algoritmul specific folosit (introsort, merge sort, etc.).
* **Total**: Complexitatea spațială este `O(N)`, deoarece vectorul rezultat poate reține toate elementele, iar spațiul auxiliar pentru sortare este, în general, la fel sau mai mic.
### Opinie Personală și Concluzii ✨
Abordarea problemei de fuzionare a intervalelor este un exemplu splendid al modului în care o idee relativ simplă – sortarea – poate transforma o provocare aparent complexă într-o soluție elegantă și eficientă. Simplitatea conceptuală, combinată cu o implementare robustă, o face o piatră de temelie în curriculumul oricărui programator.
„Algoritmii sunt ADN-ul programării: fundamentali, esențiali și dictând structura și funcționarea a tot ceea ce construim.”
Din experiența mea și observând tendințele din industria tech, stăpânirea acestui tip de probleme algoritmică este un indicator puternic al abilităților de gândire critică și rezolvare de probleme ale unui candidat. Nu este o coincidență că „Merge Intervals” apare frecvent în interviurile tehnice de la companii de top. Aceste companii caută nu doar cunoștințe de sintaxă, ci și capacitatea de a descompune o problemă, de a alege structura de date potrivită și de a optimiza soluția. Practic, este un test al modului în care mintea ta „gândește algoritmic”. O soluție eficientă la această problemă arată o înțelegere solidă a structurilor de date și a complexității algoritmilor, aspecte ce sunt indispensabile în dezvoltarea software de înaltă calitate.
Sper că acest ghid detaliat ți-a oferit claritate și încredere în abordarea Merge Intervals Problem. Exersează, experimentează și nu te teme să adaptezi această logică la propriile tale proiecte. Succes în călătoria ta algoritmică!