0261 - Intervale

Cerința

Se dau n intervale [a,b], unde a şi b sunt numere întregi. Să se afişeze acele intervale care au proprietatea că intersecţia lor cu oricare dintre celelalte n-1 intervale este mulţimea vidă

Date de intrare

Fişierul de intrare intervalein.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 ieșire

Fişierul de ieşire intervaleout.txt va conţine pe prima linie numărul k, reprezentând numărul de intervale care au proprietatea de mai sus. Urmează k linii, fiecare conţinând câte două numere întregi – capetele intervalelor determinate. Intervalele se vor afişa în ordinea în care au fost date în fişierul de intrare.

Restricții și precizări

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

Exemplul 1

Intrare

intervalein.txt

4

8 16

17 20

2 6

10 15

Ieșire

Datele de intrare corespund restricțiilor impuse

intervaleout.txt

2

17 20

2 6

Exemplul 2

Intrare

intervalein.txt

101

8 16

17 20

2 6

10 15

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#0261 - Intervale

def valideaza_date_intrare(n, intervale):
    if not (1 <= n <= 100):
        return False
    for a, b in intervale:
        if not (-30000 <= a <= 30000 and -30000 <= b <= 30000):
            return False
    return True


def gaseste_intervale_disjuncte(n, intervale):
    intervale_disjuncte = []
    for i in range(n):
        interval_curent = intervale[i]
        este_disjunct = True
        for j in range(n):
            if i != j:
                alt_interval = intervale[j]
                if not (interval_curent[1] < alt_interval[0] or interval_curent[0] > alt_interval[1]):
                    este_disjunct = False
                    break
        if este_disjunct:
            intervale_disjuncte.append(interval_curent)
    return intervale_disjuncte


def scrie_fisier_iesire(intervale_disjuncte):
    with open("intervaleout.txt", "w") as fisier_iesire:
        k = len(intervale_disjuncte)
        fisier_iesire.write(str(k) + "\n")

        for interval in intervale_disjuncte:
            fisier_iesire.write(" ".join(map(str, interval)) + "\n")


def main():
    with open("intervalein.txt", "r") as fisier_intrare:
        n = int(fisier_intrare.readline())
        intervale = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(n)]

    if valideaza_date_intrare(n, intervale):
        print("Datele de intrare corespund restricțiilor impuse")
        intervale_disjuncte = gaseste_intervale_disjuncte(n, intervale)
        scrie_fisier_iesire(intervale_disjuncte)
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)


if __name__ == "__main__":
    main()