Проверка кабинетов
Условие
В школе завхоз хочет провести несколько проверок в течение дня. Для каждого кабинета известно, в какие минуты он точно открыт: от L до R включительно.
Завхоз выбирает несколько минут времени. Проверка в выбранную минуту считается успешной для кабинета, если эта минута лежит в его отрезке [L; R].
Нужно выбрать как можно меньше минут так, чтобы для каждого кабинета нашлась хотя бы одна выбранная минута внутри его отрезка.
Формат ввода
В первой строке дано целое число n — количество кабинетов. Далее в n строках даны пары целых чисел L и R (0 ≤ L ≤ R ≤ 10^9) — отрезки времени, когда кабинет открыт.
Формат вывода
Выведите одно целое число — минимальное количество минут, которое нужно выбрать.
Ограничения
- 1 ≤ n ≤ 100000
- 0 ≤ L ≤ R ≤ 10^9
Пример
Ввод 5 1 4 2 6 8 9 3 7 9 10
Вывод 2
Решить задачу с автопроверкой на Python →
Куда дальше
- Python на олимпиадах — где языка хватает с запасом, а где начинают значить лимиты — с замерами
- Родителям: подготовка бесплатно — сколько стоит репетитор, что даёт бесплатный маршрут и как понять, что ребёнок занимается
- Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели