0263 - Intervale 2

From Bitnami MediaWiki

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 intersectare_intervale(intervale):

   # Sortează intervalele după capătul stâng
   intervale.sort(key=lambda x: x[0])
   
   # Inițializare intersecție cu primul interval
   intersecție = intervale[0]
   # Verificare intersecție cu celelalte intervale
   for interval in intervale[1:]:
       if interval[0] <= intersecție[1]:
           # Există intersecție între intervale
           intersecție = [max(interval[0], intersecție[0]), min(interval[1], intersecție[1])]
       else:
           # Nu există intersecție
           return [0, 0]
   return intersecție
  1. Citirea datelor din fișierul de intrare

with open("intervale2in.txt", "r") as f:

   n = int(f.readline())
   intervale = [list(map(int, f.readline().split())) for _ in range(n)]
  1. Calculul intervalului de intersecție

rezultat = intersectare_intervale(intervale)

  1. Scrierea rezultatului în fișierul de ieșire

with open("intervale2out.txt", "w") as g:

   g.write(" ".join(map(str, rezultat)))

</syntaxhighlight>