Домашки на вечера

В школе учитель выдал список из n небольших домашних заданий. Каждое задание занимает ровно один вечер, и за один вечер можно сделать не больше одного задания.

Про каждое задание известно число d[i] — последний день, не позже которого его можно сдать (если сделать в день d[i], это нормально). Вечера нумеруются с 1.

Нужно понять, сколько максимум заданий можно успеть сдать, если выбирать порядок выполнения самому.

Формат ввода

В первой строке дано целое число n. Во второй строке дано n целых чисел d[1], d[2], ..., d[n].

Формат вывода

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

Ограничения

• 2 ≤ n ≤ 8000
• 1 ≤ d[i] ≤ 1000000000

Пример

Ввод:

5
1 2 2 3 3

Вывод:

3

Пояснение: можно сдать задания в дни 1, 2 и 3 (например, с дедлайнами 1, 2 и 3). Остальные уже не успеют в оставшиеся вечера до своих дедлайнов.

Ключевое наблюдение: все задания одинаковые (каждое занимает ровно 1 вечер), значит важен только порядок. Если у двух заданий дедлайны a <= b, то выгоднее (или хотя бы не хуже) ставить раньше задание с дедлайном a: оно «строже», а более позднее почти всегда можно сдвинуть. Это типичный жадный обмен: если в расписании стоит b перед a, их можно поменять местами и не ухудшить выполнимость.

Отсюда приём: сортируем дедлайны по возрастанию и идём слева направо, пытаясь занять следующий свободный вечер.

План:

• Считать n и массив d.
• Отсортировать d по возрастанию.
• Завести day = 0 — сколько вечеров уже занято.
• Для каждого deadline по порядку:
• если можно поставить ещё одно задание до дедлайна, то делаем его: условие day + 1 <= deadline.
• тогда увеличиваем day и ответ.
• Вывести ответ.

Мини-сниппет проверки:

• if day + 1 <= deadline: day += 1

Сложность: сортировка O(n log n), проход O(n), память O(1) сверх массива.

Частая ошибка: пытаться «занимать именно день deadline» или хранить календарь до max(d) (он может быть до 1e9). Здесь нужен только счётчик занятых вечеров.