Cerința

Se consideră n intervale de numere întregi [A_i, B_i], 1≤i≤n. Să se determine numărul maxim de intervale care se suprapun (au cel puțin o valoare comună).

Date de intrare

Fișierul de intrare nrmaxinterv.in conține pe prima linie un numărul natural n. Pe următoarele n linii sunt descrise cele n intervale, câte un interval pe linie. Pentru fiecare interval i sunt specificate capetele sale A_i și B_i.

Date de ieșire

Fișierul de ieșire nrmaxinterv.out conține pe prima linie numărul natural NR, ce reprezintă numărul maxim de intervale care se suprapun.

Restricții și precizări

1 ≤ n ≤ 100.000
-1.000.000.000 ≤ A_i < B_i ≤ 1.000.000.000

Exemplu

nrmaxinterv.in

nrmaxinterv.out

Explicație

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema NrMaxInterv:

# include <bits/stdc++.h>
# define NMax 100001
using namespace std;

ifstream f("nrmaxinterv.in");
ofstream g("nrmaxinterv.out");

int A[NMax], B[NMax];
int n;

int main()
{
    f >> n;
    for(int i=0; i<n; ++i) {
        f >> A[i] >> B[i];
        assert(A[i] < B[i]);
    }

    sort(A, A+n);
    sort(B, B+n);

    int k = 1, Max = 1;
    int i = 1, j = 0;
    while (i < n && j < n) {
        if (A[i] <= B[j]){
            ++k; /// se deschide un nou interval
            if (k > Max){
                Max = k;
            }
            ++i;
        }
        else {
            --k;
            ++j;
        }
    }

    g << Max << '\n';

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2126 NrMaxInterv

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2126 NrMaxInterv de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2126 NrMaxInterv