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