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