Maximum trains for which stoppage can be provided

Easy
0/40
1 upvote
Asked in companies
AmazonGoogle inc

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 2
0950 1005 1
1000 1030 1
1015 1030 1
1200 1205 2
1215 1230 2
4 1
1200 1210 1
1205 1220 1
1215 1230 1
1215 1240 1
Sample Output 1:
4
2
Explanation of sample input 1:
Test Case 1:

subsequence

‘Platform number = 1’,
You can provide stoppage to at max ‘2’ train in-between ‘09:50’ to ‘10:30’. If you can give stoppage to train number ‘2’, only one train can be provided in-between ‘10:00’ to ‘10:30’ so provide stoppage to train number ‘1’ and ‘3’.
‘Platform number = 2’,
You can provide stoppage to both trains ‘4’ and ‘5’.

Return ‘ 2 (platform-1)+ 2 (platform-2) =4’.


Test Case 2:

subsequence

‘Platform number = 1’,
You can provide stoppage to only two trains either ( ‘1’, ‘3’ ) or ( ‘1’, ‘4’ ).

Return ‘2’.
Sample Input 2:
2
3 1
1000 1030 1
1050 1100 1
1100 1130 1
3 1
1000 1010 1
1000 1020 1
1000 1030 1
Sample Output 2:
3
1
Hint

Calculate the number of trains at every platform separately.

Approaches (1)
Activity Selection

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’.
Time Complexity

0(Nlog(N)), where ‘N’ is the number of trains.

 

The time complexity due to the sorting will be O(Nlog(N)).

Space Complexity

O(N), where ‘N’ is a number of trains.

 

We are storing the values of ‘arrival time’ and ‘departure time’ in another vector/list.

Code Solution
(100% EXP penalty)
Maximum trains for which stoppage can be provided
Full screen
Console