Minimum Number of Platforms Required

Given the arrival and departure times of trains at a railway station, determine the minimum number of platforms needed so that no train has to wait.

The problem can be mathematically described as follows: Given two lists of times in the format HH:MM, one for arrivals and one for departures, find the smallest integer P such that for every moment in time the number of trains at the station is at most P. In other words, if we let \( arrivals[i] \) and \( departures[i] \) denote the time (in minutes since midnight) of the i-th arrival and departure respectively, you are to compute:

\( \text{minPlatforms} = \max_{t} (\text{number of trains present at time } t) \)

where a train is considered present if its arrival time is less than or equal to t and its departure time is greater than t.

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains an integer N indicating the number of trains.
2. The second line contains N space-separated strings representing the arrival times in HH:MM format.
3. The third line contains N space-separated strings representing the departure times in HH:MM format.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of platforms required so that no train has to wait.

6
09:00 09:40 09:50 11:00 15:00 18:00
09:10 12:00 11:20 11:30 19:00 20:00

3