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

<syntaxhighlight lang="python" line="1" start="1">

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()

</syntaxhighlight>

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.