Minimum number of platforms-coding question asked by Amazon, Microsoft

Problem statement:

Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting.

Consider at any given instance of time, same platform can not be used for both departure of a train and arrival of another train. In such cases, we need different platforms.

Input Format:

Array containing arrival and departure times.

Output Format:

Minimum number of platform needed.

Sample Input 1:

AT = [900 940 950 1100 1500 1800]
DT= [910 1200 1120 1130 1900 2000]

Sample Output 1:

3

Sample Input 2:

AT = [100 200 300 400]
DT= [200 300 400 500]

Sample Output 2:

2

Constraint:

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

Approach:

First we need to sort both the arrays. When the events will be sorted, it will be easy to track the count of trains that have arrived but not departed yet. Total platforms needed at one time can be found by taking the difference of arrivals and departures at that time and the maximum value of all times will be the final answer. If(arr[i]<=dep[j]) means if arrival time is less than or equal to the departure time then- we need one more platform. So increment count as well as increment i. If(arr[i]>dep[j]) means arrival time is more than the departure time then- we have one extra platform which we can reduce. So decrement count but increment j. Update the ans with max(ans, count) after each iteration of the while loop.

Time complexity: O(nlogn)

Space complexity: O(1)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.