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 intervale4.in 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 intervale4.out 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.

Exemplu:

intervale4.in

5

2 3

4 6

3 5

8 10

7 11

intervale4.out

2

Rezolvare

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

def solve(n, intervals):

   # Sortăm intervalele în ordine crescătoare
   intervals.sort()
   
   # Inițializăm lista de intervale unite cu primul interval
   merged = [intervals[0]]
   
   # Parcurgem fiecare interval
   for current in intervals:
       # Obținem ultimul interval adăugat în lista de intervale unite
       last = merged[-1]
       
       # Dacă intervalul curent se intersectează cu ultimul interval adăugat
       if current[0] <= last[1]:
           # Actualizăm capătul drept al ultimului interval cu valoarea maximă dintre capetele drepte ale celor două intervale
           last[1] = max(last[1], current[1])
       else:
           # Dacă nu se intersectează, adăugăm intervalul curent în lista de intervale unite
           merged.append(current)
   
   # Returnăm numărul de intervale din lista de intervale unite
   return len(merged)

1. Definim numărul de intervale și intervalele inițiale

n = 5 intervals = [[2, 3], [4, 6], [3, 5], [8, 10], [7, 11]]

1. Apelăm funcția solve cu aceste valori și afișăm rezultatul pe ecran

print(solve(n, intervals))

</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.