Шешімі: Мероприятия в конференц-зале
Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия в минутах от начала суток. Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которое можно провести в конференц-зале, и максимально возможный перерыв между двумя последними мероприятиями.
В первой строке входного файла находится натуральное число $N$ ($N \le 1000$) — количество заявок. Следующие $N$ строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое число натуральное и не превосходит 1440. Используйте данные из прилагаемого файла. Запишите два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями.
Шешімін қадамдап көрсету
4 қадамСчитать все пары времени начала и окончания мероприятий.
Отсортировать мероприятия по времени окончания. Для получения максимального количества мероприятий применить жадный алгоритм: выбирать очередное мероприятие, если его начало не меньше окончания последнего выбранного.
Одновременно рассматривать варианты, сохраняющие максимальное количество мероприятий, и для каждого такого расписания вычислять перерыв между двумя последними мероприятиями как разность между началом последнего и окончанием предпоследнего.
Из полученных расписаний выбрать максимальный перерыв и вывести два найденных значения.
Определяется по данным прилагаемого входного файла.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать мероприятия пересекающимися, если окончание бір совпадает с началом другого.
Сортировать заявки по времени начала вместо времени окончания.
Максимизировать перерыв, не обеспечив максимальное количество мероприятий.
Вычислять перерыв между окончанием предпоследнего и окончанием последнего мероприятия.