시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 172 | 29 | 24 | 22.642% |
효성이가 다니는 학교에서 멀리서 통학하는 학생들의 편의를 위해서 학교와 터미널 사이를 운행하는 셔틀버스를 도입하기로 하였다. 그리고 셔틀 버스의 운행의 스케줄은 전적으로 학생들의 의견을 따르기로 하였다. 셔틀 버스의 운행 스케줄이 주어질 때 운행에 필요한 버스의 최소의 수를 계산하는 프로그램을 작성하시오. 이때 셔틀 버스를 타고 내리는 시간은 고려하지 않는다.
입력의 첫 줄에는 테스트 케이스의 개수 T(1≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 첫 줄에 터미널까지 걸리는 시간 D(1 ≤ D ≤ 120)가 분으로 주어지고, 그 다음 줄에는 학교에서 터미널로 출발하는 시간의 수 A(1 ≤ A ≤ 20)가 주어지고 그 다음에는 A개의 출발 시간이 HH:MM(HH시 MM분)의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 그 다음 줄에는 터미널에서 학교로 출발하는 시간의 수 B(1 ≤ B ≤ 20)가 주어지고 그 다음에는 B개의 출발 시간이 HH:MM의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 시간은 06:00 ~ 21:00 사이의 값이 주어지며 HH와 MM은 항상 두 자리 숫자로 주어진다(한 자리 숫자일 경우에는 앞에 0을 붙인다.). 같은 출발 장소에서 같은 시각에 출발하는 스케줄이 있을 때에는 각각의 스케줄에 다른 버스가 운행되어야 한다
각 테스트 케이스에 대해서 스케줄대로 운행하기 위해 필요한 버스의 최소의 개수를 한 줄에 하나씩 출력한다.
3 30 1 08:00 2 08:00 08:00 15 2 08:00 12:00 1 08:45 90 5 07:00 11:00 12:00 17:00 21:00 4 06:00 11:00 15:00 20:00
3 1 3