Minimum Number of Platform Needed

Easy

0/40

Average time to solve is 23m

10 upvotes

Asked in companies

Problem statement

You are given the arrival and departure times of N trains at a railway station in a day. You need to find the minimum of platforms required for the railway station such that no train waits i.e No train should wait for the platform to be clear or free.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first line of each test case contains a positive integer N which represents the number of trains that arrive at the railway station in a day.

The Second line of each test case contains N integers denoting the arrival time of all the trains.

The third line of each test case contains N integers denoting the departure time of all the trains.

Output Format :

For each test case, return the minimum number of platforms required at the railway station such that no train waits.

Note :

Representation of arrival and departure time will be in HHMM format.

Do not print anything. It has been already taken care of.

Constraints :

1 <= T <=100
1 <= N <=1000
0 <= arrival[i] <= departure[i] <= 2359

Time Limit: 1 sec

Sample Input 1 :

1
6
900 940 950 1100 1500 1800
910 1200 1120 1130 1900 2000

Sample Output 1:

Explanation of Input 1 :

During the interval [900 - 910], there will be one train.
During the interval [910 - 940], there will be no train.
During the interval [940 - 950], there will be one train.
During the interval [950 - 1100], there will be two trains, as the third train will arrive before the second train leaves.
During the interval [1100 - 1120], there will be three trains.
During the interval [1120 - 1130], there will be two trains, as the third train leaves the station.
During the interval [1130 - 1200], there will be one train.
During the interval [1200 - 1500], there will be no train.
During the interval [1500 - 1800], there will be one train.
During the interval [1800 - 1900], there will be two trains.
During the interval [1900 - 2000], there will be one train.
After the interval [2000], there will be no train.

So the number of platforms needed is 3.

Sample Input 2 :

1
3
900 1000 1200
1000 1100 1240

Sample Output 2 :

Approaches (2)

Approach 1

Approach 2

Time Complexity

Space Complexity

(100% EXP penalty)

Minimum Number of Platform Needed

Console