Задание 26 ЕГЭ по информатике · 72EC10
Мероприятия в конференц-залеВысокаяКЭС 3.10
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия в минутах от начала суток. Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которые можно провести в конференц-зале, и самое позднее время окончания последнего мероприятия.
В первой строке входного файла находится натуральное число N (N≤1000) — количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440. Запишите в ответе два числа: максимальное количество мероприятий и самое позднее время окончания последнего мероприятия. Для выполнения задания используйте данные из прилагаемого файла.
1_72EC10.zipВ первой строке входного файла находится натуральное число N (N≤1000) — количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440. Запишите в ответе два числа: максимальное количество мероприятий и самое позднее время окончания последнего мероприятия. Для выполнения задания используйте данные из прилагаемого файла.
Показать ответ
19 1362
Подсказки (3)
- В каком порядке следует рассматривать мероприятия, чтобы выбрать их максимальное количество?
- Отсортируйте мероприятия по времени окончания и последовательно выбирайте первое мероприятие, начало которого не раньше окончания уже выбранного.
- После нахождения максимального количества мероприятий среди вариантов с этим количеством выберите расписание, у которого время окончания последнего мероприятия максимально.
Решение
1. Считаем пары чисел из файла как интервалы времени проведения мероприятий.
2. Для получения максимального количества мероприятий сортируем интервалы по времени окончания и применяем жадный алгоритм: выбираем мероприятие, если его время начала не меньше времени окончания последнего выбранного мероприятия.
starti≥endlast
3. При совпадении максимального количества мероприятий сравниваем время окончания последнего мероприятия в каждом допустимом расписании и сохраняем наибольшее значение.
4. Итоговый ответ записывается в виде двух чисел: найденное максимальное количество и самое позднее время окончания последнего мероприятия.
2. Для получения максимального количества мероприятий сортируем интервалы по времени окончания и применяем жадный алгоритм: выбираем мероприятие, если его время начала не меньше времени окончания последнего выбранного мероприятия.
starti≥endlast
3. При совпадении максимального количества мероприятий сравниваем время окончания последнего мероприятия в каждом допустимом расписании и сохраняем наибольшее значение.
4. Итоговый ответ записывается в виде двух чисел: найденное максимальное количество и самое позднее время окончания последнего мероприятия.
Частые ошибки
- Считать мероприятия несовместимыми при совпадении времени окончания одного и времени начала другого.
- Сортировать интервалы только по времени начала.
- Выбирать расписание с самым поздним окончанием, не проверяя максимальность количества мероприятий.
- Учитывать только один вариант расписания и не сравнивать время окончания последнего мероприятия при одинаковом количестве событий.
Источник: Открытый банк ФИПИ
Похожие задания
26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · 3B2A3F26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · A9339F26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · B1238C26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · B4222426Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · E53C3B26Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны…Мероприятия в конференц-зале · EDE407
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.