Given a schedule containing arrival and departure time of trains in a station, find minimum number of platforms needed in the station so to avoid any delay in arrival of any train.

Trains arrival = { 2.00, 2.10, 3.00, 3.20, 3.50, 5.00 };

Trains departure = { 2.30, 3.40, 3.20, 4.30, 4.00, 5.20 };

Minimum platforms needed is 2

Train arrived at 2.00 on platform 1

Train arrived at 2.10 on platform 2

Train departed at 2.30 from platform 1

Train arrived at 3.00 on platform 1

Train departed at **3.20** from platform 1

Train arrived at **3.20** on platform 1

Train departed at 3.40 from platform 2

Train arrived at 3.50 on platform 2

Train departed at 4.00 from platform 2

Train departed at 4.30 from platform 1

Train arrived at 5.00 on platform 1

Train departed at 5.20 from platform 1

The idea is to merge arrival and departure time of trains and consider them in sorted order. (*Instead of actual merging arrival and departure of trains and then sorting them, we can also sort arrival and departure of trains and follow logic similar to merging of two sorted arrays*).

We maintain a counter to count number of trains present at the station at any point of time. The counter also represents number of platforms needed at that time.

- If train is scheduled to arrive next, we increase the counter by 1 and update minimum platforms needed if count is more than minimum platforms needed so far.

- If train is scheduled to depart next, we decrease the counter by 1.

One special case we need to handle. When two trains are scheduled to arrive and depart at the same time, we depart the train first.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef vector<double> Trains; // Function to find minimum number of platforms needed in the // station so to avoid any delay in arrival of any train. int minPlatforms(Trains arrival, Trains departure) { // maintains the count of trains int count = 0; // stores minimum platforms needed int platforms = 0; // take two indices for arrival and departure time int i = 0, j = 0; // run till train is scheduled to arrive while (i < arrival.size()) { // if train is scheduled to arrive next if (arrival[i] < departure[j]) { // increase the count of trains and update minimum // platforms if required platforms = max(platforms, ++count); // move the pointer to next arrival i++; } // if train is scheduled to depart next i.e. // (departure[j] < arrival[i]), decrease the count of trains // and move pointer j to next departure // If two trains are arriving and departing at the same time, i.e. // (arrival[i] == departure[j]) depart the train first else count--, j++; } return platforms; } // Find minimum number of platforms needed in the station to avoid any // delay in arrival of any train int main() { Trains arrival = { 2.00, 2.10, 3.00, 3.20, 3.50, 5.00 }; Trains departure = { 2.30, 3.40, 3.20, 4.30, 4.00, 5.20 }; // sort arrival time of trains sort(arrival.begin(), arrival.end()); // sort departure time of trains sort(departure.begin(), departure.end()); cout << "Minimum platforms needed is " << minPlatforms(arrival, departure); return 0; } |

`Output:`

Minimum platforms needed is 2

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
import java.util.Arrays; class Util { // Function to find minimum number of platforms needed in the // station so to avoid any delay in arrival of any train. public static int minPlatforms(double[] arrival, double[] departure) { // maintains the count of trains int count = 0; // stores minimum platforms needed int platforms = 0; // take two indices for arrival and departure time int i = 0, j = 0; // run till train is scheduled to arrive while (i < arrival.length) { // if train is scheduled to arrive next if (arrival[i] < departure[j]) { // increase the count of trains and update minimum // platforms if required platforms = Integer.max(platforms, ++count); // move the pointer to next arrival i++; } // if train is scheduled to depart next i.e. // (departure[j] < arrival[i]), decrease the count of trains // and move pointer j to next departure // If two trains are arriving and departing at the same time, // i.e. (arrival[i] == departure[j]) depart the train first else { count--; j++; } } return platforms; } // Find minimum number of platforms needed in the station to avoid any // delay in arrival of any train public static void main(String[] args) { double[] arrival = { 2.00, 2.10, 3.00, 3.20, 3.50, 5.00 }; double[] departure = { 2.30, 3.40, 3.20, 4.30, 4.00, 5.20 }; // sort arrival time of trains Arrays.sort(arrival); // sort departure time of trains Arrays.sort(departure); System.out.print("Minimum platforms needed is " + minPlatforms(arrival, departure)); } } |

`Output:`

Minimum platforms needed is 2

The time complexity of above solution is O(nlogn) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Hi, How did you calculate the time complexity of the above code to O(nlogn) ? Thanks

std::sorttakesO(nlogn)time 🙂Hi, What if:

Trains arrival = { 2.00, 2.10, 3.00, 3.20, 3.50, 5.00 };

Trains departure = {

3.40,2.30, 3.20, 4.30, 4.00, 5.20 };Instead of:

Trains departure = {

2.30,3.40, 3.20, 4.30, 4.00, 5.20 };It would be neccessary 4 plataforms, right? But the algorithm would return 2, like in the example above.

Oh, I misunderstood, it is alright, I thought departure[i] and arrival[i] was associated with a same train. Thanks, techiedelight, I really appreciate your solutions!