DEV Community

Akhil
Akhil

Posted on

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.          
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

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            |
   +----------------------------------------------+
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

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

Top comments (5)

Collapse
 
majaleksander profile image
Aleksander Maj

I always appreciate interesting coding challenges during the interview, here is my solution using some light functional methods:

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

const numPlatforms = (arrivals, departures) => (
  [
  ...arrivals.map(time => ({time, value: 1})), 
  ...departures.map(time => ({time, value: -1}))
  ].
  sort((a,b) => (a.time - b.time)).
  reduce((acc, s) => ({
    value: (acc.value + s.value),
    max: Math.max(acc.max, acc.value)
  }), {value: 0, max: 0}).
  max
);

numPlatforms(arr, dept);
Collapse
 
akhilpokle profile image
Akhil

Hi ! thanks for your solution. Could you explain the flow of execution? I am not that well versed in javascript methods.

Collapse
 
majaleksander profile image
Aleksander Maj
  1. It merges an array of arrivals with departures and adds some values (1 when the train arrives and -1 when it departures). Result of it should be an array of sth like:
    [{time: 9:00, value: 1}, ....,{time: 2000, value: -1}]

  2. Then I sort it like you did it.

  3. .reduce is loop that's going through the "timetable" and it is doing two things:

    • add 1 if train comes and subtracts if it departures
    • check what is current number of trains and save max of this value
Thread Thread
 
akhilpokle profile image
Akhil

Wow! This is so efficient! Thanks for sharing it !!

Some comments may only be visible to logged-in visitors. Sign in to view all comments.