Minimum Number of Platforms Required for a Railway/Bus Station

ByIshita Juneja

In many interviews and contests, budding programmers face unique questions that would also test their performance highly. 

Some of the sample complex yet exciting questions that you might come across are:

And so on.

Are you new to these questions, though? If so, do not worry because we are here to help you. 

In this guide, we’re specifically going to observe the minimum number of platform problems with a great example and solution approaches. 

You will also read some interesting facts on the go.

Let’s get started! 

 

What is the railway station problem all about?

The minimum platforms of a railway station is a tricky problem where the recruiters try to figure out your logical and problem-solving skills. You will receive a train’s arrival and departure times in this question. 

This train will come from a particular railway station. Now, the arrival and departure arrays denote a complete clock (24 hours). You will be asked to find how many platforms this particular train will cross to come on time. 

Here’s an example to understand this problem easily. 

Input: 

Arrival [] = {8:00, 8:40, 8:50, 10:00, 15:40, 16:00}

Departure [] = {8:10, 12:00, 10:20, 10: 30, 18:00, 20:40}

Output would be 3.

The output was given as between the time 10:00 and 10:20, one train is arriving and two trains are leaving. So we need three platforms at that time to run the trains smoothly. Unlike other trains, their arrival and departure do not disturb arriving and departing time of other trains. 

 

Methods to solve the Minimum Platforms Problem

Usually, to solve the problem, we use two solution approaches, namely,

  • Naive Method
  • Efficient Method

However, we can also use the heap method to solve the problem, and we will look into all these three methods now.

DSA Fact: Do you know a palindrome denotes a word’s pronunciation behind the same even if it is reversed? 

In the longest palindromic subsequence problem, we will find palindromes within a string. An example would be ANANA (ANANA spelled in reversed sounds the same).

 

Method 1: Naive Technique

Naive method is the easiest approach that will help you find the required number of platforms for the train to come to the railway station. In this method, we will use two nested for loops.

Firstly, the for loop (inner) is initiated. It will help us find the number of intervals that took place during the intersection at the outer for-loop intervals. After the inner loop process ends, we should change the max value of the derived interval count. 

Then we should initiate the next iteration for the for loop (outer). Once this process is done, we get the maximum value amount and that denotes the minimum number of platforms that are required.

In this method, due to the nested loop operation that is the inner and outer loop, the time used is O(n2). As there isn’t any auxiliary space used, the space taken is O(1).

 

Method 2: Efficient Technique

In the naive approach, we won’t have an efficient answer because we don’t take account of the redundancies it might cause. Notably, in the naive method, we try to find the platforms required from every index. 

We do it to make sure that no train waits on the track. But in the efficient technique, we can cut off the time spent in finding the answer by working on every index. This also cuts down the repetition (loop) process which ultimately saves time. 

Now how will we find the max number of trains? We can make use of the timestamps of arrival and departure of a train and sort them in an order. When a train comes, we will increase the train counter by 1. Similarly, when the train leaves, we will decrease by 1. By this method, we avoid repetition.

Steps:

  • Prepare a list and store the arrival and departure times of the trains.
  • Now mark every time-stamp accordingly (arrival or departure). This will help us to figure out when to increment and decrement the train counter.
  • Now use the sort method to arrange the timestamps in an order.
  • After sorting, one by one, apply iteration over every time-stamp.
  • Increment if the arrival time-stamp is there and decrease if the departure time-stamp comes.
  • At every point, maximize the result. You will find the minimum platforms required. 

DSA Fact: In this approach, we use the sorting method. Sorting helps users to decrease the amount of unnecessary comparison. It helps to arrange data in an order which will also help save time complexities. 

 

Time and space complexity:

As we have made use of the sorting method to arrange arrival and departure time stamps, the time taken is O(logn). Due to the traversal function on the array, an additional time of O(n) is utilized. Hence, the overall time taken is O(nlogn). As auxiliary space is saved, O(1) is the complexity. 

 

Method 3: Heap Technique

In the previous approach, we used the sorting method, whereas, in this approach, the heap strategy is used. Heap helps us to delete elements that are of the highest or lowest importance. Binary heaps are one of the common examples of this data structure. 

In this method, we will store the arrival and departure times of all the trains, sort them and start comparing each other to find whether a train’s arrival time is smaller than the departure time of the train that previously came. 

If the result is small, we should increment it by 1. By repeating this, we will figure out the minimum platforms needed. 

 

Conclusion

Who would have thought coders can come up with questions with railway stations? 

Now that they do exist, we hope you are now well aware of the solving approaches.

Apart from that, we hope our fun facts keep you engaged with DSA knowledge too. Feel free to visit our website to learn more.