Организация конференц-зала
Факультет инженерии ПГУ располагает большой конференц-залом для проведения мероприятий и встреч сотрудников факультета. Использование конференц-зала необходимо бронировать заранее. Поскольку зал доступен 10 часов в день и может быть несколько мероприятий, претендующих на его использование, оптимальной стратегией является максимизация количества мероприятий в день.
Предположим, что конференц-зал доступен с 0 до 10 часов (10 часов). Имея список времени начала и окончания каждого потенциального мероприятия, вам нужно написать программу, которая выберет мероприятия, которые могут быть проведены в конференц-зале (т.е. их времена не пересекаются), и обеспечит максимальное количество мероприятий в день.
Входные данные
Первая строка содержит положительное целое число n (1 ≤ n ≤ 100), которое указывает количество дней (тестовых случаев). Каждый тестовый случай состоит из времени потенциальных мероприятий (менее 20 мероприятий). Время каждого мероприятия задается 2 целыми числами, которые обозначают время начала (s) и время окончания (f), 0 ≤ s ≤ 9, 1 ≤ f ≤ 10 и s < f.
Строка, содержащая 0 0, указывает на конец каждого тестового случая. Обратите внимание, что мероприятие должно длиться как минимум 1 час.
Выходные данные
Для каждого тестового случая выведите максимальное количество мероприятий, которые могут быть проведены в конференц-зале.