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