7A. Student observation.py

"""
На первом курсе одной Школы, учится 1 ≤ N ≤ 109 студентов. При проведении экзаменов
студентов рассаживают в ряд, каждого за своей партой. Парты пронумерованы числами
от 0 до N - 1.
Известно, что студент, оставшись без наблюдения, открывает телефон и начинает искать
ответы на экзамен в поисковике Яндекса.
Поэтому было решено позвать M преподавателей наблюдать за студентами. Когда за студентом
наблюдает хотя бы один преподаватель, он стесняется и не идет искать ответы к экзамену.
Преподаватель с номером i видит студентов сидящих за партами от bi до ei включительно.
Необходимо посчитать количество студентов, которые все таки будут искать ответы
к экзамену в Яндексе

Формат ввода
В первой строке находятся два целых числа 1 ≤ N ≤ 109, 1 ≤ M ≤ 104 — число студентов
и число преподавателей соответственно. В следующих M строках содержится по два целых
числа 0 ≤ bi ≤ ei ≤ N - 1 — парты, за которыми наблюдает i-й преподаватель.

Формат вывода
Выведите одно число — количество студентов оставшихся без наблюдения.

Пример 1
Ввод
Вывод
10 3
1 3
2 4
9 9

5

Пример 2
Ввод
Вывод
10 2
1 1
1 2

8
"""

IN = -1
OUT = 1


def fun(s, N):
    """
    >>> fun([(1, 3), (2, 4), (9, 9)], 10)
    5
    >>> fun([(1, 1), (1, 2)], 10)
    8
    """

    events = [None] * len(s) * 2

    for i, (start, end) in enumerate(s):
        events[2 * i] = (start, IN)
        events[2 * i + 1] = (end + 1, OUT)  # начиная с end + 1 нет наблюдения

    events.sort()

    num = 0  # число наблюдателей за каждой партой
    not_nul = 0  # число парт с ненулевым количеством наблюдателей (когда num > 0)

    for i in range(len(events)):
        if num > 0:
            not_nul += events[i][0] - events[i - 1][0]

        _, type = events[i]
        if type == IN:
            num += 1
        elif type == OUT:
            num -= 1

    return N - not_nul


N, M = map(int, input().split())
s = [tuple(map(int, input().split())) for _ in range(M)]
print(fun(s, N))

# print(f">>> fun({s}, {N})")
# print(f"    {fun(s, N)}")


if __name__ == "__main__":
    import doctest

    doctest.testmod()