- Описание
- Решения
- Разборы
- Кодерун AI β
705. Рейсы между офисами
У компании открылся второй офис и для перемещения сотрудников между офисами было решено организовать автобусные рейсы, которые будут ездить по расписанию из первого офиса во второй и обратно. Расписание уже готово, но непонятно, каким минимальным количеством автобусов удастся обслужить все рейсы.
Расписание состоит из рейсов из первого офиса во второй и обратных рейсов. Для каждого рейса известно время отправления и время прибытия с точностью до минуты. Любой рейс полностью выполняется в течение одних календарных суток (с 00:00 до 23:59 включительно), никакой рейс не прибывает на следующий день после отправления. Каждый рейс занимает как минимум одну минуту, то есть ни один рейс не прибывает к офису назначения в ту же минуту, в которую он отправился. После прибытия автобус готов в ту же минуту отправиться в обратный рейс. Одновременно возле офиса может находиться, отправляться или прибывать любое количество автобусов. Автобусы не могут перемещаться вне расписания в течение дня. Вам не нужно учитывать подготовку к выполнению расписания следующего дня — необходимо только определить минимальное количество автобусов для обслуживания рейсов в течение одного дня.
Формат ввода
В первой строке находится число ( ) — количество рейсов из первого офиса во второй. В следующих \ строках находятся описания рейсов, по одному на строке: время отправления и время прибытия, разделенные дефисом («-»).
И время прибытия, и время отправления записаны в формате HH:MM, где HH — час (число от 0 до 23, при необходимости, дополненное ведущим нулем до двух цифр), MM — минута (число от 0 до 59, при необходимости, дополненное ведущим нулем до двух цифр).
В -й строке находится число ( ) — количество рейсов из второго офиса в первый. В следующих строках находятся описания этих рейсов в том же формате.
Формат вывода
Выведите единственное число — минимально возможное количество автобусов, достаточное для обслуживания всех рейсов.
Ограничения
- Ограничение времени
- 4 с
- Ограничение памяти
- 256 МБ
Примеры
Пример 1
4
06:45-10:20
07:36-11:26
19:00-22:35
20:08-23:58
7
06:35-10:10
07:15-11:10
11:00-14:48
14:00-17:48
15:40-19:28
18:35-22:23
20:20-23:55
7
Пример 2
2
10:00-12:00
15:00-17:00
2
12:30-14:30
17:30-19:30
1
Пример 3
2
10:10-10:11
10:10-10:11
2
10:11-10:12
10:11-10:12
2