Question

Fișierul titu.in conține numere naturale: pe prima linie un număr n (n∈[2,104]), iar pe următoarele n linii câte două numere naturale din intervalul [0,104], reprezentând capetele unor intervale închise. Numerele aflate pe oricare linie a fișierului sunt în ordine crescătoare, separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul intervalelor distincte obținute prin reuniunea celor aflate în fișier. Utilizați un algoritm eficient din punctul de vedere al timpului de executare. Exemplu: dacă fișierul are conținutul alăturat se obține reuniunea [2,7]∪[25,70]∪[80,85] și se afișează pe ecran: 3 Scrieți programul Pascal/C/C++ corespunzător cerinței și explicați în limbaj natural metoda de rezolvare, justificând eficiența acesteia. (15 puncte) 6 80 85 3 7 50 70 83 84 2 5 25 50

Answer 1

#include <fstream>

#include <iostream>

using namespace std;

bool inceput[105], sfarsit[105];

/*un element din vectorii inceput si sfarsit are valoarea de adevar daca incepe sau se termina la pozitia respectiva un interval */

int main(){

   int n;

   ifstream fin("titu.in");

   fin >> n;

   int a,b;

   for(int i = 0; i < n; i++){//O(n)

       fin >> a >> b;

       inceput[a] = true;

       sfarsit[b] = true;

   }

   fin.close();

   int d = 0, k = 0;

   for(int i = 0; i < 105; i++){//O(1)

       if(inceput[i])

           d++;

       if(sfarsit[i]){

           if((--d)==0)k++;

       }

   }

   cout << k;

}