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:
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 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.
  • 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

package org.arpit.java2blog;

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, 220, 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;
    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

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012