Vizualizare sursă pentru „3975 - Intervale AB”

== Cerinţa ==
Dându-se '''N''' intervale '''[a, b]''', calculați numărul maxim de astfel de intervale care se intersectează în cel puțin un punct.
== Date de intrare ==
Fișierul de intrare '''intervalein.txt''' conține pe prima linie numărul '''N''', iar pe următoarele '''N''' linii '''2''' numere naturale separate prin spații, reprezentând limitele intervalelor '''[a, b]'''.
== Date de ieșire ==
Fișierul de ieșire '''intervaleout.txt''' va conține pe prima linie numărul '''mx''', reprezentând numărul maxim de intervale care se intersectează în cel puțin un punct.
== Restricţii şi precizări ==
* 1 &les; N &les; 100.000
* -2.000.000.000 &les; a &les; b &les; 2.000.000.000 
== Exemplu ==
; intervalein.txt
 5
 1 5
 3 4
 -10 10
 -23 -20
 100 200
; intervaleout.txt
 Datele de intrare corespund restrictiilor impuse.
 3
<br>
== Exemplu 2 ==
; intervalein.txt
 -1
 1 5
 3 4
 -10 10
 -23 -20
 100 200
; intervaleout.txt
 Datele de intrare nu corespund restrictiilor impuse.
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_intersecting(intervals):
    # Sortăm intervalele după capătul drept
    intervals.sort(key=lambda x: x[1])

    # Inițializăm o listă pentru a stoca intervalele în curs de procesare
    current_intervals = []

    # Inițializăm numărul maxim de intervale care se intersectează
    max_inter = 0

    for interval in intervals:
        # Adăugăm intervalul curent la lista de intervale în curs de procesare
        current_intervals.append(interval)

        # Eliminăm intervalele care s-au terminat
        while current_intervals and current_intervals[0][1] < interval[0]:
            current_intervals.pop(0)

        # Actualizăm numărul maxim de intervale care se intersectează
        max_inter = max(max_inter, len(current_intervals))

    return max_inter


def main():
    # Deschidem fișierul de intrare și citim datele
    with open('intervalein.txt', 'r') as f:
        n = int(f.readline().strip())
        intervals = [list(map(int, f.readline().strip().split())) for _ in range(n)]

    # Verificăm dacă numărul de intervale respectă restricțiile
    if 1 <= n <= 100000 and all(-2000000000 <= a <= b <= 2000000000 for a, b in intervals):
        # Dacă da, calculăm numărul maxim de intervale care se intersectează
        result = max_intersecting(intervals)
        status = "Datele de intrare corespund restrictiilor impuse."
    else:
        # Dacă nu, afișăm un mesaj de eroare
        result = ""
        status = "Datele de intrare nu corespund restrictiilor impuse."

    # Scriem rezultatul în fișierul de ieșire
    with open('intervaleout.txt', 'w') as f:
        f.write(status + '\n' + str(result))


if __name__ == "__main__":
    main()

</syntaxhighlight>