Question 16 : Find minimum number of platforms required for railway station

You are given the arrival and departure time of trains reaching a particular station. 

You need to find a minimum number of platforms required to accommodate the trains at any point in time.

For example:

arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
No. of platforms required in above scenario = 4

Please note that the arrival time is in chronological order.

Solution :

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

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:

import java.util.Arrays;
 
public class TrainPlatformMain {
    public static void main(String args[])
    {
        // arr[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
        // dep[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
 
        int arr[] = {100, 140, 150, 200, 215, 400};
        int dep[] = {110, 300, 210, 230,315, 600};
        System.out.println("Minimum platforms needed:"+findPlatformsRequiredForStation(arr,dep,6));
    }
 
    static int findPlatformsRequiredForStation(int arr[], int dep[], int n)
    {
        int platform_needed = 0, maxPlatforms = 0;
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i = 0, j = 0;
 
        // Similar to merge in merge sort
        while (i < n && j < n)
        {
            if (arr[i] < dep[j])
            {
                platform_needed++;
                i++;
                if (platform_needed > maxPlatforms)
                    maxPlatforms = platform_needed;
            }
            else
            {
                platform_needed--;
                j++;
            }
        }
        return maxPlatforms;
    }
}

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

Minimum platforms needed:4

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

   

Share This

• Facebook
• Twitter
• Linkedin
• Pinterest