2. Fișierul titu2021. In conține pe prima linie un număr natural, n (nÎ[2,104]), iar pe
următoarele n linii câte două numere naturale din intervalul [-109,109], reprezentând extremitățile
câte unui interval deschis. Numerele aflate pe aceeași linie a fișierului sunt în ordine strict
crescătoare și sunt separate prin câte un spațiu. Se cere să se afișeze pe ecran numărul maxim de intervale care pot fi selectate dintre cele date în
fișier, cu proprietatea că oricare două dintre acestea au intersecția vidă. Utilizați un algoritm eficient din punctul de vedere al timpului de executare. .
Răspunsuri la întrebare
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
class Interval {
private:
int inf, sup;
public:
Interval(int _inf=0, int _sup=0) :
inf(_inf), sup(_sup) {};
int getInf() {
return inf;
}
int getSup() {
return sup;
}
bool in_interval(int x) {
if (inf <= x && x <= sup) return 1;
return 0;
}
bool operator< (const Interval& other) {
return this->sup < other.sup;
}
friend std::istream& operator>>(std::istream&, Interval&);
};
std::istream& operator>>(std::istream& inp, Interval& x) {
inp >> x.inf >> x.sup;
return inp;
}
int main() {
//Declarari
std::vector<Interval> v;
std::ifstream fin("titu2021.txt");
//Citire dimenisune
int n;
fin >> n;
//Caz special
if (n == 0) {
std::cout << 0;
return 0;
}
//Redimensionare vector
v.resize(n);
//Citire intervale
for (int index = 0; index < n; index++)
fin >> v[index];
//Aranjare intervale dupa capatul superior
std::sort(v.begin(), v.end());
//Selectam primul interval din lista
int sup_intv_curent_mx = v[0].getSup();
int contor_mx = 1;
//Adaugam intervale in ordinea in care apar daca acestea nu se intersecteaza cu intervalul curent maxim
for (int index = 1; index < n; index++) {
if (!v[index].in_interval(sup_intv_curent_mx)) {
sup_intv_curent_mx = v[index].getSup();
contor_mx++;
}
}
//Afisare rezultat
std::cout << contor_mx;
}