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

# Definim numărul de intervale și intervalele inițiale
n = 5
intervals = [[2, 3], [4, 6], [3, 5], [8, 10], [7, 11]]

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