Railway Station Problem (TCS Codevita)

July 21, 2021

Railway Station Problem

Railway station problem is one of the problem that was asked in previous year TCS Codevita Exam. In this problem we have given schedule of train and their stoppage time at a railway station and we have to find the minimum number of platform needed to accommodate every train.

Railway Station

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.

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.

 

List of Top 100 Codes

One comment on “Railway Station Problem (TCS Codevita)”


  • aneesh

    n=int(input())
    c=[]
    for i in range(n):
    k=list(map(int,input().split()))
    c.append([k[0],sum(k)])
    c.sort(key=lambda x:x[0])
    l=[[c[0]]]
    for i in range(1,len(c)):
    y=0
    for j in range(0,len(l)):
    if l[j][len(l[j])-1][1]<c[i][0]:
    l[j].append(c[i])
    y=1
    if y==0:
    l.append([c[i]])
    print(len(l))