Minimum Number of Platforms Required for a Railway Station, Bloomberg Interview question. 🚄🚄🚄

Question: Given an array of arrival and departure timings for trains at a station, find the minimum number of platforms required such that no train waits.

Example :

       arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
       dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
       Output: 3 
       Between 11:00 to 12:00 there are 3 trains present at the station.

Brute Force: O(n^2)
Brute Force approach would be to go through arrival and departure for each train, compare it with the rest of the schedule, and determine the number of platforms required.

let numPlatorms = function(arr,dep,n){
  let platforms = 1;
  let result = 1;
  for(let i=0;i<n;i++){
    platforms = 1;
    for(let j =i+1;j<n;j++){
      if ((arr[i] >= arr[j] && arr[i] <= dep[j]) || (arr[j] >= arr[i] && arr[j] <= dep[i])) {
        platforms++;
      }
    }
    result = Math.max(result,platforms);
  }
  return result;
}

let arr = [900, 940, 950, 1100, 1500, 1800];
let dept = [910, 1200, 1120, 1130, 1900, 2000];

console.log(numPlatorms(arr,dept,6));

Now let's work towards optimizing and brining the runtime down.

Optimization

Let's try to make the question even simpler, the question is asking us how many trains will have an overlapping schedule, ie their start and end timings overlap with each other.

So I want you to carefully notice this part.

For a Train A, all we care about is are there any trains in the station whose departure is after the arrival of train A, because that's the only time when we require an extra platform. If departures are before the arrival of train A, then there's no need of an extra platform.

So based on this, how about sorting departure and arrival of trains. This will be done in O(nlogn) time. And it works really well since all we care about is, are there trains whose departures are after the arrival of a train

After sorting, we just compare each arrival with departure, if it's after then we add platforms and simultaneously keep track of the number of platforms required. If it's before then we decrease the number of platforms since that train has left.

Step 1> Sort it :
arr = [900, 940, 950, 1100, 1500, 1800];
dept = [910, 1120, 1130, 1200, 1900, 2000];

Step 2> Compare arrival and departure:
we need at least 1 platform. And we shall start from index 1 for arrival and compare it with index 0 with departure since we allocated a platform which came first, now we're comparing it with the new train that just arrived with the departure of the previous train at the station.

Based on arrival and departure events here's a table:


   +----------------------------------------------+
   |                                              |
   |  Time      Event     Total Platforms Needed  |                
   |  9:00      Arrival              1            |
   |  9:10      Departure            0            |
   |  9:40      Arrival              1            |
   |  9:50      Arrival              2            |
   |  11:00     Arrival              3            |
   |  11:20     Departure            2            |
   |  11:30     Departure            1            |
   |  12:00     Departure            0            |
   |  15:00     Arrival              1            |
   |  18:00     Arrival              2            |
   |  19:00     Departure            1            |
   |  20:00     Departure            0            |
   +----------------------------------------------+

Now let's code it:

      let numPlatorms = function(arr,dep,n){
        let platforms = 1;
        let result = 1;
        arr.sort((a,b)=>a-b);            //sort all arrivals
        dep.sort((a,b)=>a-b);            //sort all departures
        let i=1;
        let j=0;
        while(i<n && j<n){
          // if arrival <= departure then increase number of platform required 
          if(arr[i]<=dep[j]){
            platforms++;
            i++;
          }else if(dep[j]<arr[i]){  // else decrease the number of platforms required
            platforms--;
            j++;
          }
          result = Math.max(platforms,result);
        }

        return result;
      }

      let arr = [900, 940, 950, 1100, 1500, 1800];
      let dept = [910, 1200, 1120, 1130, 1900, 2000];

      console.log(numPlatorms(arr,dept,6));

This is a merger interval pattern, whenever we come across a situation where we want to find a number of something required which is in turn dependent on intervals of something. We try to merge them.

I have covered similar question before here : https://dev.to/akhilpokle/minimum-number-of-arrows-to-burst-balloons-192g

I hope you understood how to solve such problems. If you've any doubts or I messed up somewhere, please do let me know in comments.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/MinimumNumberofPlatforms.js

Blog

Minimum Number of Platforms Required for a Railway Station, Bloomberg Interview question. 🚄🚄🚄

Akhil

Join Our Newsletter. No Spam, Only the good stuff.

Related