Задание 26

Файлы к заданию:

Бизнес-центру необходимо составить расписание мероприятий в конференц зале. В каждый момент времени в зале может проводиться только одно мероприятие. Организаторы мероприятий подали заявки, в которых указано время начала и время окончания их мероприятий. Из данных заявок необходимо составить расписание так, чтобы количество проводимых мероприятий было наибольшим. При этом если одна заявка закончилась, а следующая началась в то же время , то их можно ставить подряд. Входные данные. В первой строке входного файла находятся два числа через пробел: число L - общая длительность работы зала (натуральное число не превышающее 10⁹) и число N - количество поданных заявок (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа через пробел. Первое число - время начало мероприятия от начала работы зала (натуральное число, не превышающее 10⁹). Второе число - время окончания (натуральное число, не превышающее 10⁹). Запишите в ответе два числа: наибольшее возможное количество мероприятий в расписании, а также наименьшее возможное время начала последнего мероприятия. Пример входного файла: 1000 7 50 200 0 300 200 450 500 550 550 700 700 800 750 900 При таких условиях расписание можно составить из мероприятий: 50-200; 200-450; 500-550; 550-700; 700-800. Поэтому ответ для приведённого примера 5 700.