문제1160--셔틀버스

1160: 셔틀버스

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 232  통과: 32
[제출] [채점기록] [묻고답하기]

문제 설명

효성이가 다니는 학교에서 멀리서 통학하는 학생들의 편의를 위해서 학교와 터미널 사이를 운행하는 셔틀버스를 토입하기로 하였다. 그리고 셔틀 버스의 운행을 스케줄은 전적으로 학생들의 의견을 따르기로 하였다. 셔틀 버스의 운행 스케줄이 주어진 때 운행에 필요한 버스의 최소의 수를 계산하는 프로그램을 작성하시오. 이때 셔틀 버스를 타고 내리는 시간은 고려하지 않는다.

입력 설명

입력은 표준입력(standard input)을 통해 받아들인다. 입력을 첫 줄에는 테스트 케이스의 개수 T(1 ≦ ≦10)가 주어진다. 각 테스트 케이스는 첫 줄에 터미널까지 걸리는 시간 D(1 ≦ D ≦ 120)가 분으로 주어지고, 그 다음에는 A개의 출발 시간이 HH:mm의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 그 다음 줄에는 터미널에서 학교로 출발하는 시간의 수 B(1 ≦ B ≦ 20)가 주어지고, 그 다음에는 B 개의 출발 시간이 HH:MM의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 시간은 06:00 ~ 21:00 사이의 값이 주어지며 HH와 MM인 항상 두 자리 숫자로 주어진다.(한 자리 숫자일 경우에 앞에 0을 붙이다.). 같은 출발 장소에서 같은 시각에 출발하는 스케줄이 잇을 대에는 각각의 스케줄에 다른 버스가 운행되어야 한다.

출력 설명

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 스케줄대로 운행하기 위해 필요한 버스의 최소의 개수를 한 줄 하나씩 출력한다.

입력 예시 Copy

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

출력 예시 Copy

3
1
3

출처/분류