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

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

# 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)]

# Calculul intervalului de intersecție
rezultat = intersectare_intervale(intervale)

# Scrierea rezultatului în fișierul de ieșire
with open("intervale2out.txt", "w") as g:
    g.write(" ".join(map(str, rezultat)))

# Verificare restrictii
assert 1 <= n <= 100
for i in range(n):
    a, b = intervale[i]
    assert -100 <= a <= 100
    assert -100 <= b <= 100