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.
Top comments (5)
I always appreciate interesting coding challenges during the interview, here is my solution using some light functional methods:
Hi ! thanks for your solution. Could you explain the flow of execution? I am not that well versed in javascript methods.
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}]Then I sort it like you did it.
.reduceis loop that's going through the "timetable" and it is doing two things: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.