Решение: Мероприятия и перерыв
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество заявок на проведение мероприятий. Следующие $N$ строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
5 шаговДля каждой заявки обозначим время начала через $start_i$, а время окончания — через $end_i$. Две заявки $j$ и $i$ совместимы, если мероприятие $j$ заканчивается не позднее начала мероприятия $i$.
$$end_j \le start_i$$Отсортируем все заявки по времени окончания. Для каждой заявки $i$ вычислим $dp_i$ — максимальное количество мероприятий в расписании, последним из которых является мероприятие $i$.
Переберём все пары заявок. Если $end_j \le start_i$, то можно добавить мероприятие $i$ после расписания, заканчивающегося мероприятием $j$.
$$dp_i = \max(dp_i, dp_j + 1)$$Если переход образует расписание с максимальным количеством мероприятий, вычислим перерыв между двумя последними мероприятиями.
$$gap = start_i - end_j$$Среди всех расписаний с максимальной длиной выберем максимальное значение $gap$.
В ответе указываются два вычисленных по приложенному файлу числа: максимальное количество мероприятий и максимальный перерыв между двумя последними мероприятиями.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать мероприятия несовместимыми при совпадении времени окончания одного и начала другого.
Максимизировать только число мероприятий и не сравнивать перерывы между последними мероприятиями.
Вычислять перерыв как разность времён начала вместо разности начала следующего и окончания предыдущего мероприятия.
Использовать только жадный выбор самого раннего окончания без дополнительного учёта максимального перерыва.