0878 - Intervale4

Cerința

Se consideră un șir de n intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă.

Să se determine câte intervale există în șir după realizarea acestor operații.

Date de intrare

Fișierul de intrare intervale4in.txt conține pe prima linie numărul n, iar următoarele n linii câte două valori x y, reprezentând intervalele inițiale, în ordine.

Date de ieșire

Fișierul de ieșire intervale4out.txt va conține pe prima linie numărul C de intervale din șir, după realizarea operațiilor.

Restricții și precizări

• 1 ≤ n ≤ 100.000;
• pentru fiecare interval dat, x ≤ y, valori întregi care se pot reprezenta pe patru octeți.

Exemplul 1:

intervale4in.txt

5
2 3
4 6
3 5
8 10
7 11

intervale4out.txt

Datele de intrare corespund restrictiilor impuse
2

Exemplul 2:

intervale4in.txt

intervale4

intervale4out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

def validare(numere, intervals):           # functia de validare a datelor de intrare

    if numere < 1 or numere > 100000:
        raise ValueError

    for intervall in intervals:
        if len(intervall) != 2 or intervall[0] > intervall[1]:
            raise ValueError

    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


def solve(intervals):                     # functia de rezolvare
    # Sortăm intervalele în ordine crescătoare
    intervals.sort()

    # Inițializăm lista de intervale unite cu primul interval
    unite = [intervals[0]]

    # Parcurgem fiecare interval
    for curent in intervals:
        # Obținem ultimul interval adăugat în lista de intervale unite
        ultim = unite[-1]

        # Dacă intervalul curent se intersectează cu ultimul interval adăugat
        if curent[0] <= ultim[1]:
            # Actualizăm capătul drept al ultimului interval cu valoarea maximă dintre capetele drepte ale celor două intervale
            ultim[1] = max(ultim[1], curent[1])
        else:
            # Dacă nu se intersectează, adăugăm intervalul curent în lista de intervale unite
            unite.append(curent)

    # Returnăm numărul de intervale din lista de intervale unite
    return len(unite)


if __name__ == '__main__':
    file_in = open("intervale4in.txt", "r")         # declararea fisierelor
    file_out = open("intervale4out.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    # din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
    try:
        n = int(file_in.readline())      # citirea numarului de intervale
        intervale = []
        for _ in range(n):
            interval = list(map(int, file_in.readline().split()))
            intervale.append(interval)

        validare(n, intervale)                 # apelul functiei de validare
        file_out.write(str(solve(intervale)))             # apelul functiei de rezolvare

    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")

    file_in.close()
    file_out.close()

Explicație

Intervalele din șirul inițial sunt: [2,3] [4,6] [3,5] [8,10] [7,11].

1.Se reunesc intervalele [4,6] [3,5] și se obține șirul [2,3] [3,6] [8,10] [7,11]. 2.Se reunesc intervalele [2,3] [3,6] și se obține șirul [2,6] [8,10] [7,11]. 3.Se reunesc intervalele [8,10] [7,11] și se obține șirul [2,6] [7,11]. La final în șir se află două intervale.