2126 - Nr Max Interv

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

Încărcare soluție

Lipește codul aici

​import sys

sys.stdin = open('nrmaxinterv.in', 'r')

sys.stdout = open('nrmaxinterv.out', 'w')

a = [0] * 100001

b = [0] * 100001

n = int(input())

for i in range(1, n + 1):

    a[i], b[i] = map(int, input().split())

a.sort()

b.sort()

i = 1

j = 1

cntmax = 0

cnt = 0

while i <= n and j <= n:

    if a[i] <= b[j]:

        i += 1

        cnt += 1

        if cnt > cntmax:

            cntmax = cnt

    else:

        j += 1

        cnt -= 1

print(cntmax)