Задача к ЕГЭ по информатике на тему «Программирование - Обработка целочисленной информации с использованием сортировки» №1

Как известно, во время проведения всетибетской олимпиады по морфемике требуются наблюдатели. Известно, что время начала олимпиады — $begin$ и время окончания — $end$ , то есть время проведения олимпиады — это полуинтервал $[begin,end)$ . Среди студентов вуза, принимающего олимпиаду был составлен список из $N$ студентов-волонтеров, которые смогут наблюдать за учениками и времена $a$ и $b$ , с которого и по которое они смогут проводить наблюдение (полуинтервал $[a,b)$ ).

Требуется оторвать от учебы как можно меньше студентов-волонтеров, чтобы в каждый момент олимпиады за учениками присматривал хотя бы один студент, при этом смена первого студента-волонтера произошла как можно позже, с момента старта олимпиады. Важно чтобы данный состав наблюдателей смог проконтролировать проведение олимпиады.

Входные данные

В первой строке содержится три натуральных числа — количество наблюдателей $N$ , время начала олимпиады — $begin$ и время окончания — $end$ , то есть время проведения олимпиады — это полуинтервал $[begin,end)$ .

В последующих $N$ строках содержится два числа — $a,b$ , где $a$ — время начала, $b$ — время окончания работы наблюдателя, то есть наблюдатель работает в течение полуинтервала $[a,b)$ .

Выходные данные

Программа должна вывести в ответе два числа — минимальное количество наблюдателей, которое в состоянии проконтролировать олимпиаду, и время работы первого наблюдателя с момента начала олимпиады.

Пример входных данных:

$5$ $2$ $10$

$1$ $4$

$1$ $3$

$3$ $8$

$7$ $10$

$10$ $11$

Наблюдение полностью обеспечивают наблюдатели, работающие в полуинтервалы $[1,4),[3,8),[7,10)$ . Время работы первого наблюдателя с начала экзамена $4 − 2 = 2$ . Ответ: $3$ $2$

f = open(’27b.txt’)
n, begin, end = map(int, f.readline().split())
data = sorted([[int(i) for i in f.readline().split()] for i in range(n)])
diff = 0
maxim = 0
ans = 0
time = 0

# проходим по списку наблюдателей
for i in range(n):
    # если время начала работы наблюдателя меньше или равно времени начала олимпиады
    if data[i][0] <= begin:
        # и если время окончания работы наблюдателя больше времени начала олимпиады
        if data[i][1] > begin:
            # и если разница между временем окончания работы наблюдателя и временем начала олимпиады больше текущей разницы
            if data[i][1] - begin > diff:
                # обновляем разницу и время окончания работы первого наблюдателя
                diff = data[i][1] - begin
                maxim = data[i][1]
    # если время начала работы наблюдателя больше времени начала олимпиады
    else:
        # и если еще не был назначен ни один наблюдатель
        if ans == 0:
            # вычисляем время работы первого наблюдателя
            time = maxim - begin

        # обновляем начало олимпиады, разницу и количество наблюдателей
        begin = maxim
        diff = 0
        ans += 1

        # если олимпиада закончилась, прерываем цикл
        if maxim >= end:
            break

print(ans, time)

Ответ: 59 290

Задача к ЕГЭ по информатике на тему «Программирование — Обработка целочисленной информации с использованием сортировки» №1