**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.

**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.

**Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.**

**Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.**

**HAPPY CODING**😁

**Solution**

**( C ++ )**

#### Recommended Codevita Problems

Count Pairs | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Lift | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Number Distancing | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Critical Planets | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Prime Time Again | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Minimum Gifts | TCS CodeVita 9 Solution ( Zone 1 ) 2020

Minimize The Sum | TCS CodeVita 9 Solution ( Zone 1 ) 2020

If you have any doubts regarding this problem or need the solution in other programming languages then leave a comment down below .

Can't it be the job sequencing problem of greedy approach? sorting the trains in terms of their arrival time and compare? please reply

ReplyDeleteI am having the same thought🤔...

Deletecan we take the arrival time as key for dict and the halt time as value and then we would just sort the keys and according to that we might be able to predict the platforms can you please post python solution

ReplyDeleteI tried this approach only but every time it was giving time limit exceeded.

ReplyDelete