| Входной файл: | input.txt | Ограничение времени: | 2 сек | |
| Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
Вы прекрасно знаете, что в ЛКШ.Зима~2016 лекции читают лучшие преподаватели мира. К сожалению, лекционных аудиторий у нас не так уж и много, поэтому каждый преподаватель составил список лекций, которые он хочет прочитать ЛКШатам. Чтобы ЛКШата, утром идя на завтрак, увидели расписание лекций, необходимо его составить прямо сейчас. И без вас нам здесь не справиться.
У нас есть список заявок от преподавателей на лекции для одной из аудиторий. Каждая заявка представлена в виде временного интервала [si, fi) — время начала и конца лекции. Лекция считается открытым интервалом, то есть какая-то лекция может начаться в момент окончания другой, без перерыва. Необходимо выбрать из этих заявок такое подмножество, чтобы суммарно выполнить максимальное количество заявок. Учтите, что одновременно в лекционной аудитории, конечно же, может читаться лишь одна лекция.
В первой строке вводится натуральное число N, не более 1000 — общее количество заявок на лекции. Затем вводится N строк с описаниями заявок — по два числа в каждом si и fi. Гарантируется, что si < fi. Время начала и окончания лекции — натуральные числа, не превышают 1440 (в минутах с начала суток).
Выведите одно число — максимальное количество заявок, которые можно выполнить.
si < fi
N ≤ 1000
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|