0353 - Spectacole

Cerinţa

La un festival sunt programate n spectacole. Pentru fiecare se cunoaște momentul de început și momentul de sfârșit, exprimate prin numere naturale. Un spectator dorește să urmărească cât mai multe spectacole în întregime.

Determinați numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună.

Date de intrare

Fişierul de intrare spectacolein.txt conţine pe prima linie numărul n. Pe fiecare dintre următoarele n linii se află câte două numere naturale X Y, reprezentând momentul de început și momentul de sfârșit al unui spectacol.

Date de ieşire

Fişierul de ieşire spectacoleout.txt va conţine pe prima linie numărul S, reprezentând numărul maxim de spectacole care pot fi urmărite, fără să se suprapună.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• momentele de început și sfârșit ale spectacolelor sunt numere naturale mai mici decât 1.000.000
• pentru fiecare spectacol, X < Y
• dacă momentul de început al unui spectacol și momentul de sfârșit al altui spectacol coincid, pot fi urmărite ambele spectacole

Exemplul 1

spectacolein.txt

10
5 14
14 17
8 13
13 15
15 17
3 6
4 7
6 9
11 14
10 11

spectacoleout.txt

Datele de intrare corespund restrictiilor impuse.
5

Explicație

Pot fi alese, de exemplu, spectacolele: 3 6, 6 9, 10 11, 11 14 și 14 17.

Exemplul 2

spectacolein.txt

igrij

spectacoleout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

# Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat
def validare(n_validare, spectacole_validare):
    # Verificăm dacă n este în intervalul 1-100
    if n_validare < 1 or n_validare > 100:
        raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-100
    for spectacol in spectacole_validare:    # Parcurgem lista de spectacole
        # Verificăm dacă momentele de început și sfârșit ale spectacolelor sunt în intervalul specificat
        if spectacol[0] >= 1000000 or spectacol[1] >= 1000000 or spectacol[0] >= spectacol[1]:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse.\n")


# Funcția numar_spectacole determină numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună
def numar_spectacole(n_numar, spectacole_numar):
    # Sortăm spectacolele în funcție de momentul de sfârșit
    spectacole_numar.sort(key=lambda x: x[1])
    # Inițializăm numărul de spectacole cu 1
    nr_spectacole = 1
    # Inițializăm momentul de sfârșit al ultimului spectacol urmărit
    sfarsit_ultim = spectacole_numar[0][1]
    # Parcurgem lista de spectacole
    for i in range(1, n_numar):
        if spectacole_numar[i][0] >= sfarsit_ultim:
            # Urmărim spectacolul curent
            nr_spectacole += 1
            sfarsit_ultim = spectacole_numar[i][1]
    return nr_spectacole


if __name__ == '__main__':
    file_in = open("spectacolein.txt", "r")
    file_out = open("spectacoleout.txt", "w")

    try:
        # Citim numărul de spectacole
        n_main = int(file_in.readline())
        # Citim momentele de început și sfârșit ale spectacolelor
        spectacole_main = [list(map(int, file_in.readline().split())) for _ in range(n_main)]
        # Validăm datele de intrare
        validare(n_main, spectacole_main)
        # Determinăm numărul maxim de spectacole care pot fi urmărite
        nr_spectacole_main = numar_spectacole(n_main, spectacole_main)
        # Scriem numărul maxim de spectacole care pot fi urmărite în fișierul de ieșire
        file_out.write(str(nr_spectacole_main) + '\n')

    # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
    # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse.")