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.


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.
Time complexity : O(NLogN)
Below diagram will make you understand above code better:

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

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


Add Comment