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

Discussion (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 Author

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 Author

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

Collapse
kenpeter profile image
Comment marked as low quality/non-constructive by the community. View Code of Conduct
kenpeter

practice.geeksforgeeks.org/problem...

@akhil for the brute force solution.
I found that it is not able to pass all test cases.

e.g.
1026 0445 0145 0555 0710 1712 1105 0506 0531 1930 0220 0611 0553 0053 0401 2000 0225 1359 1159 0120 1857 0740 0253 0303 0740 1434 1407 0807 0423 0500 0851 0809 0527 0123 1117 0023 1050 1613 1025 1225 0826 0422 0221 0028 0515 0401 1241 0038 0315 1007 0508 1054 0803 0333 0011 0225 0137 0030 0344 0036 0841 1419 0552 0422 0337 1222 1422 0010 0258 1434 0538 0153 0808 0347 0104 1136 0302 0357 0938 2015 0403 0258 0736 1057 1547 0531 1642 2333 0511 1301 1059 0638 0117 0314 0905 1314 1103 0356 0006 0.................

Its Correct output is:
434

And Your Code's output is:
779