Last Updated: 12 Feb, 2021

Maximum trains for which stoppage can be provided

Easy

Asked in companies

Solve now

Problem statement

You are given the ‘n’ number of trains and ‘m’ number of a platform for a station. Every train has an associate with ‘arrival time’, ‘departure time’, and ‘platform’ number.

Your task is to determine the maximum number of trains for which you can provide a stoppage at the station.

You can provide stoppage to only one train at platform ‘x’ between ‘arrival time’ to ‘departure time’ of the current train.

If ‘arrival time’ and ‘departure time’ is 1015 then consider as 10:15.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘n’ and ‘m’, where ‘n’ denotes the number of trains and ‘m’ denotes the number of platforms.
Next ‘n’ lines contain three space-separated integers ‘arrival time’, ‘departure time’, and ‘platform’ number.

Output Format:

For every test case, return the maximum number of trains for which stoppage can provide.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraint :

1 <= T <= 100
1 <= N <= 3000 
1 <= M <= 3000 
0000 <= Arrival Time <= 2359
0000 <= Departure Time <= 2359
1 <= Plateform Number <= M 

Where ‘T’ represents the number of test cases, ‘N’ is the number of trains, ‘M’ is the number of platforms, and ‘Arrival Time’ and ‘Departure Time’ is ‘HH:MM’ time of arrival and departure time of trains.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Logic same as Activity selection problem.

For every platform,

separate every train according to the platform number and store it in the ‘platform’ vector/list.

Sort the train according to the departure time for every platform, so that we can decide which train is overlapping with other trains.

Create a 2-d vector/list called it ‘platform’.
Now for each ‘i’ from ‘0’ to ‘n-1’,
- Insert trains ‘arrival time’ and ‘departure time’ as a pair according to platform number of a current train, Suppose the value of ‘trains[i][2]’(platform number of ‘i-th’ train) is ‘4’ then insert in platform ‘4’.
- So add ‘trains[i][0]’(arrival time of ‘i’ train) and ‘trains[i][1]’(departure time of ‘i-th’ train) in ‘platform[ trains[i][2]]’.
Sort every vector/list of every platform according to their departure time. Now for each ‘i’ from ‘1’ to ‘m’
- Sort the ‘platform[i]’ according to the second value.
Use ‘ans =0’ to store the answer.
Now for each ‘i’ from ‘1’ to ‘m’ for every platform
- ‘ans= ans+1’ always select the first train of every platform
- Ans mark as select or ‘lastSelected = platform [i][0][1]’
- Iterate another loop ‘j’ for every train of the particular platform ‘i-th’ from ‘1’ to length of ‘platform[i]’
  - If the start time of this current train ( platform[i][j][0]) is greater than or equal to the departure time (platform[i][1])of the previously selected train ‘lastSelected’ choose then this train and do-
    - ‘ans = ans+1’.
    - ‘lastSelected = platform[i][j][1]’
In the end, return ‘ans’.

Solve now