Railway Station is one of the problem asked in TCS CodeVita 2020. In this post, we will solve this problem using python along will algorithm and explanation of the python code.
Given schedule of trains and their stoppage time at a Railway Station, find minimum number of platforms needed.
If Train A’s departure time is x and Train B’s arrival time is x, then we can’t accommodate Train B on the same platform as Train A.
1 <= N <= 10^5
0 <= a <= 86400
0 < b <= 86400
Number of platforms > 0
First line contains N denoting number of trains.
Next N line contain 2 integers, a and b, denoting the arrival time and stoppage time of train.
Single integer denoting the minimum numbers of platforms needed to accommodate every train.
The earliest arriving train at time t = 5 will arrive at platform# 1. Since it will stay there till t = 15, train arriving at time t = 10 will arrive at platform# 2. Since it will depart at time t = 12, train arriving at time t = 13 will arrive at platform# 2.
Platform #1 can accommodate train 1.
Platform #2 can accommodate train 2.
Note that the departure of train 1 is same as arrival of train 2, i.e. 6, and thus we need a separate platform to accommodate train 2.
Algorithm for Railway Station Codevita
The algorithm to solve Railway Station problem is given below.
Step 1: Start. Step 2: Take number of trains as input in variable N. Step 3: Initialize two empty lists arrival and departure. arrival list stores the arriving time and departure time of trains. Step 4: Read arrival time and stoppage time for N trains. Append the arrival values in arrival list and append the (arrival + stoppage) values in departure list. Step 5: Sort both arrival and departure lists in ascending order. Step 6: Set value of variables platform_needed to 1, result to 1, i to 1 and j to 0. Step 7: Repeat from step 8 to 10 until i is less than n and j is less than n, Step 8: If arrival[i] is less than or equal to departure[j] then increment platform_needed by 1 and i by 1. i.e. platform_needed = platform_needed + 1 i = i + 1 This means that, another train is arriving while the previous train has not left the platform (or previous train has not departed). So, we need one more platform to accommodate the train which is arriving. Step 9: Else if arrival[i] is greater than departure[j] then decrement platform_needed by 1 and increment j by 1. i.e. platform_needed = platform_needed - 1 j = j + 1 This means that, the platform is currently empty and the train arriving can stay at the platform. Step 10: If platform_needed is greater than result then assign the value of result to platform_needed. Step 11: The required number of platform is the final value stored in variable result. Step 12: End.
Also Read: Factor of 3 Codevita 9 Solution in Python
Program to Solve Railway Station Problem in Python
def total_platform(arrival, departure, n): arrival.sort() departure.sort() platform_needed = 1 result = 1 i = 1 j = 0 while(i<n and j<n): if(arrival[i] <= departure[j]): #platform is not empty platform_needed += 1 i += 1 elif(arrival[i] > departure[j]): #platform is empty platform_needed -= 1 j += 1 if(platform_needed > result): result = platform_needed return result # N contains total number of trains # arrival list contains the arrival time # departure list contains the (arrival + stoppage) time N = int(input()) arrival =  departure =  for i in range(0, N): # a and b are arrival and stoppage time (not departure time) for a train respectively a, b = list(map(int, input().split())) arrival.append(a) departure.append(a + b) print(total_platform(arrival, departure, N))
3 10 2 5 10 13 5 2
- At first, we will take number of trains as input in variable
N = input()
- Then, we will be taking arrival time and stoppage time as input. We have to loop for N trains.
for i in range(0, N): a, b = list(map(int, input().split())) arrival.append(a) departure.append(a + b)
Arrival time and stoppage time is taken as input separated with a space. Those two values are split when a space is encountered using
split() and assigned to
b. After that, arrivial time i.e a is appended in
arrival variable and (a + b) which is the departure value is appended to
total_platform(arrival, departure, n)
Now, let’s move to the function which is used to calculate number of platforms.
- This function accepts three variables.
Arguments: arrival - list of arrival times of trains (integers) departure - list of departure time of trains (integers) n - number of trans (integer) Returns: result - number of platforms_needed (integer)
- Sort both arrival and departure lists using
sort(). This helps to compare the arrival time and departure time of trains to check if the platform is empty or not easily.
- Then, initialize all the required variables.
platform_needed = 1 result = 1 i = 1 j = 0
- Here, we will check if the platform is empty. For this, we will repeat until i is less than n and j is less than n.
while(i<n and j<n):. . .
- Inside the loop, we will check if the arrival[i] is less than or equals to departure[j].
if(arrival[i] <= departure[j]): platform_needed += 1 i += 1
This means that, another train is arriving while the previous train has not departed. So, we increase the
- Or we check if the platform is empty by,
elif(arrival[i] > departure[j]): #platform is empty platform_needed -= 1 j += 1
If there is any free platform, we decrease the platform_needed by 1.
- Finally we check if the platform_needed is greated than result or not, if yes, the value of platform_needed is assigned to result.
if(platform_needed > result): result = platform_needed
- Final answer is stored in result and the
Explore more TCS CodeVita Solution in Python and C Programming