Решение: Расписание мероприятий
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия в минутах от начала суток. Если время начала одного мероприятия меньше времени окончания другого, провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, провести можно оба. Определите максимальное количество мероприятий, которые можно провести в конференц-зале, и самое позднее время окончания последнего мероприятия в этом случае.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$). Следующие $N$ строк содержат пары натуральных чисел, не превосходящих 1440, — время начала и время окончания мероприятий. Для выполнения задания используйте данные из прилагаемого файла.
Решение по шагам
4 шагаПредставим каждую заявку как интервал [начало, конец]. Условие совместимости двух последовательных мероприятий: начало следующего должно быть не меньше окончания предыдущего.
$$s_{next} \ge e_{last}$$Отсортируем все заявки по времени окончания. Жадно выбираем очередную заявку, если её время начала не меньше времени окончания последней выбранной заявки.
После просмотра всех заявок количество выбранных мероприятий будет максимальным. Среди вариантов с максимальным количеством требуется запомнить самое позднее время окончания последнего мероприятия.
Числовой ответ нельзя вычислить без содержимого прилагаемого входного файла.
Требуются данные из прилагаемого входного файла: количество мероприятий и самое позднее время окончания.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Запрещают мероприятие, начинающееся ровно в момент окончания предыдущего.
Сортируют заявки по времени начала вместо времени окончания.
Выбирают самое длинное мероприятие, хотя для максимального количества нужно выбирать мероприятие с ближайшим временем окончания.
Пытаются использовать приведённый пример вместо данных из файла.