Minimum Number of Platforms Required for a Railway/Bus Station

Approach(Efficient)

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing.So the redundancy in our above approach is that we are finding the number of platforms needed from each index such that no train waits and maximize the answer. If we make some observations we can avoid finding the number of platforms needed from each index and maximizing it repetitively.

Carefully observe that we will get the maximum number of platforms when the maximum number of trains arrive and wait during a particular time interval. Once we make this observation, the rest of the solution will become very easy to think about.

So, to find the maximum number of trains at any point of time, we can take the time stamps, i.e, arrival and departure time-stamps one by one in the sorted order. As soon as a train arrives we increment the train counter and once it departs, we can decrement the train counter. At each point, we can maximize the number of platforms needed.

Following this approach will definitely improve the efficiency of the algorithm because we don’t require any repetitive checks.   

Now we can formulate our approach:

1. Put the arrival and departure times in another list and mark each time-stamp as arrival or departure so that we can decide to increment/decrement the train counter.
2. Sort the list of timestamps.
3. Iterate over each time-stamp one by one.
4. Increment the counter if it’s an arrival time stamp, else decrement the counter.
5. At each point maximize the answer.    

Let’s look at the Code.

CODE IN C++(Efficient)

//C++ program to find the minimum number of platforms needed
#include <bits/stdc++.h>
using namespace std;


// function that returns minimum number of platforms Needed
int minPlatformsNeeded(vector<int> &arr, vector<int> &dep, int N) {
    int minPlatforms = 0; // minimum number of platforms
    // vector storing all arrival and departure time_stamps
    vector<pair<int, char>> time_stamps;
    // 'a' --> arrival
    // 'd' --> departure
    for(int time_s: arr) time_stamps.push_back({time_s, 'a'});
    for(int time_s: dep) time_stamps.push_back({time_s, 'd'});
   
    // sort time_stamps by values
    sort(time_stamps.begin(), time_stamps.end());
   
    // train counter
    int train_counter = 0;
   
    // iterate over each time stamp
    for(pair<int, char> t: time_stamps) {
        if(t.second=='a') train_counter++;   // increment if it's arrival time stamp
        else train_counter--; // decrement if it's departure time stamp
        minPlatforms = max(minPlatforms, train_counter); // maximise the answer
    }
    return minPlatforms;
}


int main() {
    // The number of arrivals and departures
    int N = 6;
    // The arrival time stamps
    vector<int> arr{ 900, 940, 950, 1100, 1500, 1800 };
   
    // The departure time stamps
    vector<int> dep{ 910, 1200, 1120, 1130, 1900, 2000 };
   
    cout<<"The minimum number of platforms needed are/is: ";
    cout<<minPlatformsNeeded(arr, dep, N)<<'\n';
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The minimum number of platforms needed are/is: 3

Complexity Analysis

Time Complexity: O(N*LogN)

Since we are sorting the set of intervals, which takes most of the time, it takes O(N*LogN) time.

Space complexity: O(N) at the worst case, as we are using auxiliary space to store all arrival and departure times.

Hence we reached an efficient solution from a quadratic solution. 

Frequently Asked Questions

Q1. Does a greedy algorithm always work?

Answer)  No, a greedy algorithm does not always work. To solve a problem via a greedy algorithm, you need to have intuitive proof in your mind, at least to lead to the correct solution. To show when it doesn’t work, you can think of a counter-example that will help rule out the greedy algorithm.

Q2. Why is sorting important?

Answer) Sorting is a very useful technique because we can reduce a significant number of comparisons. With reference to the question discussed in this blog, we moved from an exponential solution to an O(N*LogN) solution. This is sufficient to explain the power of sorting.

Q3. What is a comparator?

Answer) Comparator is an important concept. It is a function object that helps to achieve custom sorting depending on the problem requirements. 

Key Takeaways

This article taught us how to solve the problem of the Minimum Number of Platforms Required for a Railway/Bus Station. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, and proper code in detail.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out how we can apply sorting to simplify our task and make fewer comparisons. Testing a greedy algorithm as early as possible is a good practice as there is no guarantee that it will always work. Hence, if it does not work, you could rule it out and not follow a similar approach to solve the problem.

Now, we recommend you practice problem sets based on the concepts of Minimum Number of Platforms Required for a Railway/Bus Station to master your fundamentals. You can get a wide range of questions similar to the problem Minimum Number of Platforms Required for a Railway/Bus Station on Coding Ninjas Studio.