Решение: Мероприятия в конференц-зале
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество заявок на проведение мероприятий. Следующие $N$ строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Для выполнения задания используйте данные из прилагаемого файла.
В ответе укажите два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями в минутах.
Решение по шагам
5 шаговСчитаем мероприятия совместимыми, если начало следующего мероприятия не меньше окончания предыдущего.
Отсортируем заявки по времени окончания и применим жадный алгоритм: последовательно выбираем мероприятие, которое начинается не раньше окончания последнего выбранного.
Полученная последовательность имеет максимальное возможное число мероприятий.
Чтобы найти максимальный перерыв между двумя последними мероприятиями среди всех оптимальных последовательностей, сохраняем варианты состояний с максимальным количеством выбранных мероприятий и для каждого состояния максимизируем разность между началом последнего мероприятия и окончанием предпоследнего.
Числовые значения ответа определяются по данным прилагаемого входного файла.
По данным прилагаемого файла
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Сортируют мероприятия по времени начала, а не по времени окончания.
Считают мероприятия пересекающимися при совпадении окончания одного и начала другого.
Максимизируют перерыв без предварительного обеспечения максимального количества мероприятий.
Вычитают время начала последнего мероприятия из времени окончания предпоследнего.