Решение: Мероприятия в конференц-зале
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия в минутах от начала суток. Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество заявок на проведение мероприятий. Следующие $N$ строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПредставим каждую заявку как интервал [начало, окончание]. Мероприятия совместимы, если начало следующего не меньше окончания предыдущего.
Для максимизации количества мероприятий применяем жадный алгоритм: сортируем интервалы по времени окончания и выбираем очередной интервал, если он начинается не раньше окончания последнего выбранного.
$$start_i \ge end_{last}$$Сохраняем все варианты, в которых количество выбранных мероприятий максимально. Для каждого такого варианта вычисляем перерыв между двумя последними мероприятиями.
$$gap = start_{last} - end_{previous}$$Из полученных значений выбираем максимальный перерыв. Численные значения зависят от данных в приложенном входном файле.
Численный ответ определяется по данным прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Запрещают мероприятиям соприкасаться, хотя начало одного может совпадать с окончанием другого.
Сортируют заявки по времени начала вместо времени окончания.
Максимизируют только перерыв, не обеспечив максимальное количество мероприятий.
Вычитают время окончания последнего мероприятия из времени начала предпоследнего.