Minimum Number of Platforms
You have been given two arrays, 'AT' and 'DT', representing the arrival and departure times of all trains that reach a railway station.

Your task is to find the minimum number of platforms required for the railway station so that no train needs to wait.

Note :

1. Every train will depart on the same day and the departure time will always be greater than the arrival time. For example, A train with arrival time 2240 and departure time 1930 is not possible. 2. Time will be given in 24H format and colons will be omitted for convenience. For example, 9:05AM will be given as "905", or 9:10PM will be given as "2110". 3. Also, there will be no leading zeroes in the given times. For example, 12:10AM will be given as “10” and not as “0010”.

Input Format

The first line of input contains an integer 'T' representing the number of test cases. The first line of each test case contains an integer 'N', representing the total number of trains. The second line of each test case contains 'N' single-spaced separated elements of the array 'AT', representing the arrival times of all the trains. The third line of each test case contains 'N' single-spaced separated elements of the array 'DT', representing the departure times of all the trains.

Output Format:

For each test case, return the minimum number of platforms required for the railway station so that no train needs to wait.

Note :

You don't need to print the output, it has already been taken care of. You just need to implement the given function.

Follow up :

Try to solve the problem in O(N) time and O(1) space.

Constraints:

1

Question

Minimum Number of Platforms

You have been given two arrays, 'AT' and 'DT', representing the arrival and departure times of all trains that reach a railway station.

Your task is to find the minimum number of platforms required for the railway station so that no train needs to wait.

Note :

1. Every train will depart on the same day and the departure time will always be greater than the arrival time. For example, A train with arrival time 2240 and departure time 1930 is not possible.

2. Time will be given in 24H format and colons will be omitted for convenience. For example, 9:05AM will be given as "905", or 9:10PM will be given as "2110".

3. Also, there will be no leading zeroes in the given times. For example, 12:10AM will be given as “10” and not as “0010”.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer 'N', representing the total number of trains.

The second line of each test case contains 'N' single-spaced separated elements of the array 'AT',  representing the arrival times of all the trains.

The third line of each test case contains 'N' single-spaced separated elements of the array 'DT', representing the departure times of all the trains.

Output Format:

For each test case, return the minimum number of platforms required for the railway station so that no train needs to wait.

Note :

You don't need to print the output, it has already been taken care of. You just need to implement the given function.

Follow up :

Try to solve the problem in O(N) time and O(1) space.

Constraints:

1 <= T <= 10
1 <= N <= 50000
0 <= AT[i] <= DT[i] <= 2359

Where 'AT[i]' and 'DT[i]' are the elements of the arrival and the departure arrays respectively.

Time limit: 1 sec

Accepted Answer

The idea is to use the sorted arrival and departure times of trains and count the total number of platforms needed at a time . Maintain a counter to count the total number of trains present at the station at any point.
If the train is scheduled to arrive next, increase the counter by one and update the minimum platforms needed if the count is more than the minimum platforms needed so far.
If the train is scheduled to depart next, decrease the counter by 1.
Time Complexity : O(nlogn)

Accepted Answer

Using an additional array

The main idea behind this approach is to use an array, 'PLATFORMS', to store the number of platforms required at different points of time. Now, since the time range is from 0 to 2359 in the 24 hour format, we declare the array 'PLATFORMS' with a size of 2360 (as we need values from 0 to 2359) and all values initialized to 0.

Now, we traverse both the arrays together and do the following :

For all points of time between the arrival and departure of each train (both inclusive), we increment the number of platforms by 1 i.e.
for all points of time >= ‘AT[i]’ and <= ‘DT[i]’

PLATFORMS[time]++

Now, whenever we increment the number of platforms at any point of time (as discussed in the above step), we update the answer if the number of platforms is greater than the answer.

Space Complexity: O(1)Explanation:

O(1)

Since constant additional space is required, thus space complexity will be O(1).

Time Complexity: OtherExplanation:

O(N * 2360), where ‘N’ is the number of trains.

Since the traversal of the arrival and the departure arrays takes O(N) time and in the worst case, for each train, we might traverse the entire platform array (from 0 to 2359). This will happen when the arrival and departure times for each train are 0 and 2359 respectively. Thus, the overall time complexity will be O(N * 2360).

Accepted Answer

Using sorting

The main idea behind this approach is to consider all the events in the sorted order. Once the events are in the sorted order, we find the number of trains at any time by keeping track of the trains that have arrived but not yet departed. The minimum number of platforms required will be the maximum number of trains at any time.

The steps are as follows:

Sort the array ‘AT' and ‘DT’.
Use two pointers ‘i’ and ‘j’, both initialized to 0, to traverse the arrays ‘AT’ and ‘DT’ respectively. Also, we use the variable 'MIN_NUM_OF_PLATFORMS' to denote the minimum number of platforms required and the variable 'CUR_NUM_OF_PLATFORMS' to denote the current number of platforms required at any given time.
Run a loop while ‘i’ < ‘N’ and ‘j’ < ‘N’ and compare the elements ‘AT[i]’ and ‘DT[j]’:
- If ‘AT[i]’ <= ‘DT[j]’, then one more platform is needed. Thus, 'CUR_NUM_OF_PLATFORMS' = 'CUR_NUM_OF_PLATFORMS' + 1 and ‘i’ = ‘i’ + 1.
- Else one less platform is needed. Thus, 'CUR_NUM_OF_PLATFORMS' = 'CUR_NUM_OF_PLATFORMS' -1 and 'j' = 'j' + 1
Update 'MIN_NUM_OF_PLATFORMS' if 'CUR_NUM_OF_PLATFORMS' is greater than 'MIN_NUM_OF_PLATFORMS' i.e. 'MIN_NUM_OF_PLATFORMS' = max('MIN_NUM_OF_PLATFORMS', 'CUR_NUM_OF_PLATFORMS')
Return 'MIN_NUM_OF_PLATFORMS' as the answer.

Space Complexity: O(1)Explanation:

O(1)

Since no additional space is required, Thus the space complexity will be O(1).

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’ is the number of trains.

Since sorting of both the arrays takes O(N * log(N)) time. Also, we are traversing both the arrays once which takes O(N + N) time. Thus, the overall complexity is O(N * log(N) + N + N) = O(N * log(N)).

Accepted Answer

Using cumulative sum

The main difference between this approach and the previous one is that instead of looping through the 'PLATFORMS' array for every train, we just increment the number of platforms at the time of arrival and decrement the number of platforms after the departure of every train.

Just like the previous approach, we use an array, 'PLATFORMS', to store the number of platforms required at different points of time. Now, since the time range is from 0 to 2359 in the 24 hour format, we declare the array 'PLATFORMS' with a size of 2361 (as we need values from 0 to 2360) and all values initialized to 0.

Now, we traverse both the arrays together and do the following :

At the time of arrival, increase the count of 'PLATFORMS' in the array.
At the time of departure, we decrease the count of platforms just after the departure in the array i.e. if the departure time is 900, we reduce the value of 'PLATFORMS'[900 + 1] by 1.

After this traversal, we start calculating the cumulative sum (as cumulative sum will provide the required number of platforms for all points of time) and at every point of time we update the answer if the current number of platforms is greater than the answer.

Space Complexity: O(1)Explanation:

O(1)

Since constant additional space is required, thus the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N' is the number of trains.

Since the traversal of the arrival and the departure arrays takes O(N) time and the final traversal of the array platforms takes O(2360) time. Thus the overall time complexity is O(N + 2360) = O(N).

You have been given two arrays, 'AT' and 'DT', representing the arrival and departure times of all trains that reach a railway station.

Your task is to find the minimum number of platforms required for the railway station so that no train needs to wait.

Note :

Input Format

Output Format:

Note :

Follow up :

Constraints:

Top SAP Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern