Minimum Number of Platforms Required for a Railway/Bus Station

aniket verma
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss how to find the Minimum Number of Platforms Required for a Railway/Bus Station. Such problems do come in interviews as well as in many contests. Before solving the problem, it’s recommended to have a good understanding of sortings and its applications. In this Blog we will dive deep into each detail to get a firm hold over the application of sorting in problems.  

Let’s look at the problem statement.

Given a list of arrival and departure times of trains that reach a railway station. The task is to find the minimum number of railway platforms required such that no train waits.

Let’s understand the problem using an example.

Input:  N and arrival and departure times of length N, 

    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

Explanation: The minimum number of railway platforms needed is 3 because the maximum number of trains is 3 from 11:00 to 11:20.

Approach(Naive)

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to start from each index and find the number of overlapping intervals. We can maximize this value by computing the number of overlapping intervals from each index and updating it in each iteration.  

So the naive/basic approach could be formulated as:

  1. For each index, compute the number of overlapping intervals.
  2. Keep updating the maximum value in each iteration.
  3. Finally, return the maximum value. 

Now let’s look at the PseudoCode.

PseudoCode

Algorithm

___________________________________________________________________

procedure findMinimumPlatforms(arr, dep, N):

___________________________________________________________________

1.    minPlatforms ← 1 #initially the maximum number of platforms needed is 1.

2.    for time_i = 0 to N-1 do   # from every time at index i 

3.        platforms_needed ← # for each index min platform is at least 1.  

4.    for time_j = time_i+1 to N-1 do      

5.         if overlap(arr[time_i], dep[time_i], arr[time_j], dep[time_j]) == True do

6.               platforms_needed ← platforms_needed + 1

7.             end if

8.        end for

9.        minPlatforms ← max(minPlatforms, platforms_needed)

10.  end for

11.  return minPlatforms

12end procedure

___________________________________________________________________

CODE IN C++

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


// function which returns a boolean value if 2 intervals overlap or not
bool overlap(int arr_i, int dep_i, int arr_j, int dep_j) {
    return (arr_i >= arr_j and arr_i <= dep_j) or (arr_j >= arr_i and arr_j <= dep_i);
}


// 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
    // from each index find the number of platforms_needed 
    for (int i = 0; i < N - 1; ++i) {
        int platforms_needed = 1; // at least one platform is needed
        for (int j = i + 1; j < N; ++j) {
            // if the time intervals overlap increment the number of platforms needed
            if (overlap(arr[i], dep[i], arr[j], dep[j]))
                platforms_needed++;
        }
        minPlatforms = max(minPlatforms, platforms_needed);
    }
    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;
}

 

Output

The minimum number of platforms needed are/is:  3

Complexity Analysis

Time Complexity: O(n2)

This is because we iterate through all indices for each index. Hence it’s O(n2).

Space complexity: O(1) at the worst case because no extra space is used.

The above algorithm works in O(n2) time which is pretty slow. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

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;
}

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 CodeStudio

Was this article helpful ?
0 upvotes