Minimum number of platforms required for a railway station

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Problem:

You are given arrival and departure time of trains reaching to a particular station. You need to find minimum number of platforms required to accommodate the trains at any point of time.
For example:

Please note that arrival time is in chronological order.

Solution :

If you notice we need to find maximum number of trains that can be on the station with the help of arrival and departure time.

Solution 1:

You can iterate over all intervals and check how many other intervals are overlapping with it but that will require o(N^2) time complexity.

 Solution 2:

We will use logic very much similar to merge sort.

• Sort both arrival(arr) and departure(dep) arrays.
• Compare current element in arrival and departure array and pick smaller one among both.
• If element is pick up from arrival array then increment platform_needed.
• If element is pick up from departure array then decrement platform_needed.
• While performing above steps, we need track count of maximum value reached for platform_needed.
• In the end, we will return maximum value reached for platform_needed.

Java program for Minimum number of platform required for a railway station

When you run above program, you will get below output: