Cerința

Se consideră n intervale de numere întregi [Ai, Bi], 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 Ai și Bi.

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 ≤ Ai < Bi ≤ 1.000.000.000

Exemplu

nrmaxinterv.in

5
1 4
0 3
8 12
5 9
5 11

nrmaxinterv.out

3

Explicație

#include <bits/stdc++.h>

using namespace std;

ifstream cin("nrmaxinterv.in");
ofstream cout("nrmaxinterv.out");

int a[100001] , b[100001];

int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i] >> b[i];
    sort(a+1 , a+n+1);
    sort(b+1 , b+n+1);
    int i = 1 , j = 1;
    int cntmax=0 , cnt=0;
    while(i <= n && j <= n)
    {
        if(a[i]<=b[j])
        {
            i++ , cnt++;
            if(cnt > cntmax)
                cntmax=cnt;
        }
        else
            j++ , cnt--;
    }
    cout << cntmax;
    return 0;
}