Задание 26 ЕГЭ по информатике

Для проведения ЕГЭ требуются наблюдатели. На сайте профи.ру есть список наблюдателей и время, в которое они могут работать. Требуется нанять как можно меньше наблюдателей, чтобы в каждый момент экзамена за учениками присматривал хотя бы один наблюдатель, при этом смена первого наблюдателя произошла как можно позже, с момента старта ЕГЭ.

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

В первой строке файла содержится количество наблюдателей $N$, время начала ЕГЭ – $start$ и время окончания – $end$, то есть время ЕГЭ $[start, end)$. В следующих $N$ строках содержится по два числа $a$, $b$, где $a$ – время начала, $b$ – время окончания работы наблюдателя, то есть наблюдатель работает в промежуток времени $[a, b)$.

В задаче гарантируется, что данный состав наблюдателей сможет проконтролировать ЕГЭ.

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

Типовой пример организации входных данных

5 2 10

1 4

1 3

3 8

7 10

10 11

Ответ: 3 2.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/12478_26.txt