3975 - Intervale AB

Cerinţa

Dându-se N intervale [a, b], calculați numărul maxim de astfel de intervale care se intersectează în cel puțin un punct.

Date de intrare

Fișierul de intrare intervalein.txt conține pe prima linie numărul N, iar pe următoarele N linii 2 numere naturale separate prin spații, reprezentând limitele intervalelor [a, b].

Date de ieșire

Fișierul de ieșire intervaleout.txt va conține pe prima linie numărul mx, reprezentând numărul maxim de intervale care se intersectează în cel puțin un punct.

Restricţii şi precizări

• 1 ⩽ N ⩽ 100.000
• -2.000.000.000 ⩽ a ⩽ b ⩽ 2.000.000.000

Exemplu

intervalein.txt

5
1 5
3 4
-10 10
-23 -20
100 200

intervaleout.txt

Datele de intrare corespund restrictiilor impuse.
3

Exemplu 2

intervalein.txt

-1
1 5
3 4
-10 10
-23 -20
100 200

intervaleout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line> def max_intersecting(intervals):

   # Sortăm intervalele după capătul drept
   intervals.sort(key=lambda x: x[1])

   # Inițializăm o listă pentru a stoca intervalele în curs de procesare
   current_intervals = []

   # Inițializăm numărul maxim de intervale care se intersectează
   max_inter = 0

   for interval in intervals:
       # Adăugăm intervalul curent la lista de intervale în curs de procesare
       current_intervals.append(interval)

       # Eliminăm intervalele care s-au terminat
       while current_intervals and current_intervals[0][1] < interval[0]:
           current_intervals.pop(0)

       # Actualizăm numărul maxim de intervale care se intersectează
       max_inter = max(max_inter, len(current_intervals))

   return max_inter

def main():

   # Deschidem fișierul de intrare și citim datele
   with open('intervalein.txt', 'r') as f:
       n = int(f.readline().strip())
       intervals = [list(map(int, f.readline().strip().split())) for _ in range(n)]

   # Verificăm dacă numărul de intervale respectă restricțiile
   if 1 <= n <= 100000 and all(-2000000000 <= a <= b <= 2000000000 for a, b in intervals):
       # Dacă da, calculăm numărul maxim de intervale care se intersectează
       result = max_intersecting(intervals)
       status = "Datele de intrare corespund restrictiilor impuse."
   else:
       # Dacă nu, afișăm un mesaj de eroare
       result = ""
       status = "Datele de intrare nu corespund restrictiilor impuse."

   # Scriem rezultatul în fișierul de ieșire
   with open('intervaleout.txt', 'w') as f:
       f.write(status + '\n' + str(result))

if __name__ == "__main__":

   main()

</syntaxhighlight>