Minimum platforms required

Let us discuss a popular interview question-related DSA. The question is about ‘finding the minimum number of Platforms required for a railway/bus station’. There can be various ways to ask this question may be with different words or with additional complexity. I always tell this to my friends who ask me for interview tips. Listen to the question completely, ask questions, and make sure you understand the question correctly before solving the problem. Let me start with a version of the problem commonly used.

Problem definition:

The objective is to find the optimal number of platforms required to be built with a given train schedule to ensure no train has to wait.
The arrival and departure times can be represented in 2 arrays arrival & departure. The task is to find the minimum number of platforms required for the railway station. Always ask for sample input/outputs. If not, show your understanding with an example and verify you are solving the right problem. Let us take the below sample scenario.

Sample input:

arrival[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}, 
departure[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} 

Sample output:
3

How to approach this?

We should be good starting with a brute-force or naive method where you want to build 1 platform for all incoming trains. But you don’t want to waste a lot of resources. We need to find the right number of platforms to be built. This type of problem is typically called an optimization problem.

The core idea for this problem is to find the maximum number of trains that can stay in the station together. If you build that many platforms, no train/bus has to wait.

Now, If we plot the train’s stay per the given sample schedule, we can see there are a maximum of three trains (between 9:40 to 12:00). If we build 3 platforms, we should be good to fit all trains without waiting time.

Solution

Now we know the solution is to find the max number of trains that can stay together at the station at any given time. How to programmatically solve this one? i.e., how to write an algorithm?

Start with the question — How will you do it manually?

Maybe I will go keep a counter and increment it every time a train arrives and decrement when a train leaves. The max value of this counter at any point will give the required no.of platforms. We can apply the technique to solve this programmatically with the below steps.

How to find this maximum number programmatically?

There is no single to solve a problem with computers. There are popular techniques that can be applied. We will cover them in a later post. For this question, we choose a pattern of identifying the right data structure to solve the problem.

The need here is to hold the list of trains as they arrive and remove the first leaving time. In other words, we need to add elements to the list in the order of arrival time and remove them in the order of departure time. Also, the list’s maximum size at any time will give us the required maximum size.

Try to attempt with different data structures: arrays, linked-list, stacks, and queues won’t solve them. HEAP (priority queues) can help. If we push the elements in arrival time (with the value of departure time), the heap will ensure it will return the next lowest value. This can be compared, and this might solve the problem. Let us write down the steps (algorithm). Also, validate it once before sharing it with the interviewer (like the one below). Your problem-solving skill will be measured in this part of the interview.

Algorithm:

1. Sort the arrays based on arrival time

2. Push the first element from departure[] array (i.e departure time of the first arrived train) 
in an heap queue and Initialize a counter to 1

3. Iterate over the elements in arrival[] - 2nd element to last
   - Check if arrival[i] <= top element in heapq (departure time of the first train in the queue)
   - If true (we have another train arriving before a train leaves), then increment the counter by 1
   - Else pop() the element from heapq (we have a platform to occupy for the new train)
   - push the dep[i] into the heapq

4. Return counter

Implementation (python):

Once you have alignment on the algorithm or approach, the interviewer will ask you to write a program for it. With solid proficiency in a programming language, it should be a reasonably straightforward task. The python program for the above algorithm is given below. Our programming skills will be measured in this part of the interview.

import heapq

def findPlatform(arr, dep, n):
 arr2 = []
 # Store the arrival and departure time
 for i in range(n):
 arr2.append([arr[i], dep[i]])
 arr2.sort() # Sort trains based on arrival time
 p = []
 count = 1
 heapq.heappush(p, arr2[0][1])
 for i in range(1, n):
 # Check if arrival time of current train
 # is less than or equals to departure time
 # of previous train
 if p[0] >= arr2[i][0]:
 count += 1
 else:
 heapq.heappop(p)
 heapq.heappush(p, arr2[i][1])
 # return the count of number of platforms required
 return count
 
 
if __name__ == “__main__”:
 arr = [900, 940, 950, 1100, 1500, 1800]
 dep = [910, 1200, 1120, 1130, 1900, 2000]
 n = len(arr)
 print(findPlatform(arr, dep, n))

Output
3

Algorithmic analysis

Once you have a program/algorithm, the next question is, what is the complexity of time and space? Be prepared to answer this. Again there is no trick or shortcuts here. Understanding the algorithms and how to arrive at the complexity is important. I will cover how to get them with different code paths in a future post. For now, the above program has:

Time complexity: O(n log n)
Space complexity: O(n)