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 ⩽ N ⩽ 100.000
• -2.000.000.000 ⩽ a ⩽ b ⩽ 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

Exemplu 2

intervalein.txt

-1
1 5
3 4
-10 10
-23 -20
100 200

intervaleout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

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