Type Here to Get Search Results !

Railway Station | TCS CodeVita 9 Solution ( Zone 1 ) 2020 | By CodingHumans |

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





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

Post a comment

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

    ReplyDelete
  2. can 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

    ReplyDelete
  3. I tried this approach only but every time it was giving time limit exceeded.

    ReplyDelete
* Please Don't Spam Here. All the Comments are Reviewed by Admin.

Top Post Ad

Below Post Ad