Мероприятия и перерыв
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале, и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество заявок на проведение мероприятий. Следующие $N$ строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Для выполнения задания используйте данные из прилагаемого файла.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Какие два мероприятия можно проводить последовательно? Учитывайте, что окончание первого может совпадать с началом второго.
2Наводящая — какие числа считатьуровень 2 из 3
Отсортируйте заявки по времени окончания и для каждой заявки найдите максимальное число мероприятий, которые могут завершаться этим мероприятием.
3Прямая — фактически решениеуровень 3 из 3
Для каждой пары совместимых мероприятий $j$ и $i$, где $end_j \le start_i$, рассмотрите переход $dp_i = dp_j + 1$. При переходе запоминайте перерыв $start_i - end_j$ как возможный перерыв между двумя последними мероприятиями.