ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1203. Научная конференция

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Работа научной конференции обычно разделена на несколько одновременно проходящих секций. Например, может быть секция параллельных вычислений, секция визуализации, секция сжатия данных и так далее.
Очевидно, одновременная работа нескольких секций необходима, чтобы уменьшить время научной программы конференции и иметь больше времени на банкет, чаепитие и неофициальные обсуждения. Однако интересные доклады могут проходить одновременно в разных секциях.
Участник записал расписание всех докладов, интересных ему. Он просит вас определить максимальное количество докладов, которые он сможет посетить.

Исходные данные

Первая строка содержит количество 1 ≤ N ≤ 100 000 интересных докладов. Каждая из следующих N строк содержит два целых числа Ts и Te, разделённых пробелом (1 ≤ Ts < Te ≤ 30 000). Эти числа — время начала и конца соответствующего доклада. Время задано в минутах от начала конференции.

Результат

Выведите максимальное количество докладов, которые участник может посетить. Участник не может посетить два доклада, идущих одновременно, и любые два доклада, которые он посещает, должны быть разделены хотя бы одной минутой. Например, если доклад кончается в 15, следующий доклад, который может быть посещён, должен начинаться в 16 или позже.

Пример

исходные данныерезультат
5
3 4
1 5
6 7
4 5
1 3
3
Автор задачи: Магаз Асанов
Источник задачи: Соревнование команд УрГУ, март 2002