Дано количество учебных занятий, проходящих в одной аудитории. Для каждого из них указано время начала и конца. Нужно составить расписание, в соответствии с которым в классе можно будет провести как можно больше занятий.
Если возможно несколько оптимальных вариантов, то выведите любой. Возможно одновременное проведение более чем одного занятия нулевой длительности.
В первой строке задано число занятий. Оно не превосходит 1000.
Далее для каждого занятия в отдельной строке записано время начала и конца, разделённые пробелом. Время задаётся одним целым числом h, если урок начинается/заканчивается ровно в h часов. Если же урок начинается/заканчивается в h часов m минут, то время записывается как h.m.
Гарантируется, что каждое занятие начинается не позже, чем заканчивается. Указываются только значащие цифры.
Выведите в первой строке наибольшее число уроков, которое можно провести в аудитории. Далее выведите время начала и конца каждого урока в отдельной строке в порядке их проведения.
|
5 9 10 9.3 10.3 10 11 10.3 11.3 11 12 |
3 9 10 10 11 11 12 |
|
3 9 10 11 12.25 12.15 13.3 |
2 9 10 11 12.25 |
|
7 19 19 7 14 12 14 8 22 22 23 5 21 9 23 |
3 7 14 19 19 22 23 |