Railway Station CodeVita Solution in Python

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.

Problem Description

Given schedule of trains and their stoppage time at a Railway Station, find minimum number of platforms needed.
Note –
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.

Constraints

1 <= N <= 10^5
0 <= a <= 86400
0 < b <= 86400
Number of platforms > 0

Input

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.

Output

Single integer denoting the minimum numbers of platforms needed to accommodate every train.

Time Limit

1

Examples

Example 1

Input
3
10 2
5 10
13 5

Output
2

Explanation

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.

Example 2

Input
2
2 4
6 2

Output
2

Explanation

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))

Output

3
10 2
5 10
13 5
2

If you are new to python, check out our python tutorials and example programs with explanation.
Tutorial – Python Tutorial
Examples – Python Program Examples

Explanation

• At first, we will take number of trains as input in variable N.

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 a and b. After that, arrivial time i.e a is appended in arrival variable and (a + b) which is the departure value is appended to departure variable.

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.

arrival.sort()
departure.sort()

• 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 platform_needed by 1.

• 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 result is returned.

return result

More Examples

Explore more TCS CodeVita Solution in Python and C Programming