№595399091
Бизнес-центру необходимо составить расписание мероприятий в конференц зале. В каждый момент времени в зале может проводиться только одно мероприятие. Организаторы мероприятий подали заявки, в которых указано время начала и время окончания их мероприятий. Из данных заявок необходимо составить расписание так, чтобы количество проводимых мероприятий было наибольшим. При этом если одна заявка закончилась, а следующая началась в то же время, то их можно ставить подряд.
Входные данные.
В первой строке входного файла находятся два числа через пробел: число L - общая длительность работы зала (натуральное число не превышающее 109) и число N - количество поданных заявок (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа через пробел. Первое число - время начало мероприятия от начала работы зала (натуральное число, не превышающее 109). Второе число - время окончания (натуральное число, не превышающее 109).
Запишите в ответе два числа: наибольшее возможное количество мероприятий в расписании, а также наименьшее возможное время начала последнего мероприятия.
Пример входного файла:
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.