Minimum Platforms Problem

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

Formally, you are provided with an integer \( n \) representing the number of trains and \( n \) pairs of integers, where each pair represents the arrival and departure times of a train. Your goal is to determine the minimum number of platforms required at the station so that all trains can arrive and depart without conflict.

The mathematical idea behind the problem can be expressed as follows: Let \( A = [a_1, a_2, \dots, a_n] \) be the sorted arrival times and \( D = [d_1, d_2, \dots, d_n] \) be the sorted departure times. Then, by scanning both arrays with two pointers, you compute the maximum number of trains at the station simultaneously, which equals the minimum required platforms.

inputFormat

The first line contains an integer \( n \), the number of trains.

Each of the following \( n \) lines contains two space-separated integers representing the arrival and departure times of a train.

Example:

6
900 910
940 1200
950 1120
1100 1130
1500 1900
1800 2000

outputFormat

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

6
900 910
940 1200
950 1120
1100 1130
1500 1900
1800 2000

3