ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Отборочный турнир сезона «Осень — 2020» > задача:


H. Макс и фестиваль настольных игр

Отборочный турнир сезона «Осень — 2020»

Старт: 31.окт.2020 в 14:00:00
Финиш: 08.ноя.2020 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и выбор операции
• B. Макс и сонник
• C. Макс и оригинальный никнейм
• D. Макс и выгодные инвестиции --- 2
• E. Макс и снежный ком
• F. Макс и морской бой
• G. Макс и элемент паззла
• H. Макс и фестиваль настольн...
• I. Макс и жонглёры
• J. Макс и вставка букв

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и фестиваль настольных игр
Макс и фестиваль настольных игр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В городе открылся фестиваль настольных игр. В рамках фестиваля издатели игр проведут $$$N$$$ мероприятий, на каждом из которых можно будет сыграть в различные настольные игры. Макс скачал расписание фестиваля и выяснил, что $$$i$$$-е мероприятие начнётся в момент времени $$$L_i$$$ и закончится в момент времени $$$R_i$$$.

Макс хочет посетить как можно больше различных мероприятий, чтобы сыграть в максимально возможное количество игр. На партию в любой игре требуется одна единица времени. Закончив играть в игру на одном мероприятии, Макс может сразу отправиться на следующее и начать играть там.

Помогите Максу определить, сколько различных мероприятий он сможет посетить.

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

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 10^5$$$) — количество мероприятий.

Следующие $$$N$$$ строк описывают мероприятия. Каждая из них содержит целые числа $$$L_i$$$ и $$$R_i$$$ ($$$0 \le L_i < R_i \le 10^9$$$) — соответственно время начала и окончания мероприятия.

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

Выведите одно целое число — максимальное число мероприятий, на которых Макс сможет сыграть в игру.

Примеры

Входные данные
5
0 2
1 2
0 1
1 3
2 3
Выходные данные
3
Входные данные
8
1 2
0 5
2 3
1 2
4 5
7 8
6 8
6 7
Выходные данные
6

Для отправки решений необходимо выполнить вход.

www.contester.ru