Minimum Railway Platforms

You are given the arrival and departure times of n trains at a railway station. The times are specified in the HHMM format. Your task is to compute the minimum number of platforms required at the station so that no train has to wait.

Note: A train arriving exactly when another departs is not considered to be overlapping. Use efficient sorting and greedy techniques to solve this problem.

Mathematical Explanation:

Let \( A = [a_1, a_2, \dots, a_n] \) be the sorted list of arrival times and \( D = [d_1, d_2, \dots, d_n] \) be the sorted list of departure times. Find the smallest number \( P \) such that at any time the number of trains present \( N(t) \) satisfies \( N(t) \leq P \).

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 1000), the number of trains. Each of the following n lines contains two space-separated integers representing the arrival and departure times in HHMM format.

outputFormat

Output a single integer representing the minimum number of platforms required at the station so that no train waits.

3
900 910
940 1200
950 1120

2