Vizualizare sursă pentru „2126 - Nr Max Interv”


= Cerința =
Se consideră <code>n</code> intervale de numere întregi <code>[A<sub>i</sub></code>, <code>B<sub>i</sub>]</code>, <code>1≤i≤n</code>. 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 <code>nrmaxinterv.in</code> conține pe prima linie un numărul natural <code>n</code>. Pe următoarele <code>n</code> linii sunt descrise cele <code>n</code> intervale, câte un interval pe linie. Pentru fiecare interval <code>i</code> sunt specificate capetele sale <code>A<sub>i</sub></code> și <code>B<sub>i</sub></code>.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>
* <code>-1.000.000.000 ≤ A<sub>i</sub></code> <code>< B<sub>i</sub></code> <code>≤ 1.000.000.000</code>

= Exemplu: =
<code>nrmaxinterv.in</code>
 5
 1 4
 0 3
 8 12
 5 9
 5 11
<code>nrmaxinterv.out</code>
 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)