0263 - Intervale 2

Cerinta

Se dau n intervale [a,b], unde a şi b sunt numere întregi. Să se determine intervalul rezultat prin intersectarea intervalelor date.

Date de intrare

Fişierul de intrare intervale2in.txt conţine pe prima linie numărul n, iar pe următoarele n linii câte două numere întregi, separate prin spaţii, reprezentând capetele unui interval.

Date de iesire

Fişierul de ieşire intervale2out.txt va conţine pe prima linie cele două numere care reprezintă intervalul intersecție, separate printr-un spațiu, sau valoarea 0, dacă intersecția celor n intervale este mulțimea vidă.

Restrictii si precizari

• 1 ⩽ n ⩽ 100
• pentru fiecare interval dat [a,b], -100 ⩽ a , b ⩽ 100

Exemplul 1

intervale2in.txt

5

-7 10

3 20

-5 5

0 12

-8 30

intervale2out.txt

Datele introduse corespund restrictiilor impuse

3 5

Exemplul 2

intervale2in.txt

3

-2.5 1

100 0

6.3 17,2

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def intersecare_intervale(intervale):

   # Sortăm intervalele după capătul inferior
   intervale.sort(key=lambda x: x[0])

   # Inițializăm intervalul de intersecție cu primul interval
   intersecție = intervale[0]

   # Parcurgem celelalte intervale și actualizăm intervalul de intersecție
   for interval in intervale[1:]:
       intersecție = [max(intersecție[0], interval[0]), min(intersecție[1], interval[1])]

       # Dacă capătul inferior devine mai mare decât capătul superior, intersecția este vidă
       if intersecție[0] > intersecție[1]:
           return [0, 0]

   return intersecție

def main():

   with open("intervale2.txt", "r") as f_in:
       # Citim numărul de intervale
       n = int(f_in.readline())

       # Citim intervalele
       intervale = [list(map(int, f_in.readline().split())) for _ in range(n)]

   # Determinăm intervalul de intersecție
   rezultat = intersecare_intervale(intervale)

   # Scriem rezultatul în fișierul de ieșire
   with open("intervale2.txt", "w") as f_out:
       f_out.write(f"{rezultat[0]} {rezultat[1]}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>