Lift
Problem Description
In a building there are some lifts. Optimize the allocation of lifts.
Say there are N requests and M lifts. Minimize the maximum request waiting time.
Rules of lift allocation
1) One needs to assign indexes to lifts. i.e. decide lift #1, lift #2, lift #3, etc apriori.
2) Since all N requests are known apriori decide the initial (at time t = 0) location of lift such that it will help in minimizing waiting time.
3) Even if all the N requests time are known apriori, other than initial time, i.e. t = 0, the waiting lifts cannot be moved towards target floor until the request is actually issued.
4) After a request is issued for optimality calculation, even a lift is in transit it can be considered for serving that request.
5) If at any moment, more than one lift can serve the request with same waiting time, give preference to the lift with lower index. i.e. If Lift #2 and Lift #4 can serve a particular request in 2 seconds, then prefer Lift #2 over Lift #4.
6) Neglect the time required to get in and get out of a lift.
7) Once a lift starts serving a request it would not stop in between. If would finally stop at destination of that request.
8) The speed of lift is 1 floor/second.
Constraints
0 <= T <= 86400.
0 <= S, D <= 100.
1 <= N, M <= 1000.
Input
First line contains 2 integers, N and M, representing the number of requests and number of lifts in the building respectively.
Next N lines contain 3 integers, T, S, and D, representing the timestamp of request, source floor, destination floor respectively.
Output
Print single integer representing the waiting time
Time Limit
1
Examples
Example 1
Input
3 2
0 2 3
4 2 5
6 7 3
Output
3
Explanation
There are 3 requests and 2 lifts.
Initially at time t = 0, both the lifts, lift #1 and lift #2 will be at floor 2 (Initial allocation).
Request #1 and Request #2 can be responded instantly, i.e. waiting time = 0.
Lift #1 will get unallocated at floor 3 at time t = 1.
Lift #1 can move only after the next request is actually received at time t = 4, if required. Relate this with Rule #3 mentioned in problem description.
Lift #2 will get unallocated at floor 5 at time t = (4 + 3) = 7.
Now, if Lift #1 is used to respond request #3, waiting time would be 4 seconds since Lift#1 is at floor #3 and will need 4 seconds to reach floor #7.
In this case, waiting time of all requests - {0,0,4} and the maximum waiting time is 4.
Instead, if Lift #2 is used to respond request #3, waiting time would be calculated as follows
Lift #2 will get unallocated at time t = 7, so we will have to wait 7-6 = 1 seconds for lift #2 to complete it's previous request.
Time needed for Lift #2 to travel from floor #5 to floor #7 = 7-5 = 2 seconds. Therefore, total waiting time = 1 + 2 = 3 seconds.
In this case, waiting time of all requests - {0, 0, 3} and the maximum waiting time is 3.
As we have to minimize the maximum waiting time, since 2nd option is yielding lesser waiting time than 1st option, 2nd option is the answer.
Therefore, the output is 3.
Example 2
Input
5 3
0 2 3
4 2 5
6 7 3
3 5 6
2 5 7
Output
1
Explanation
There are 5 requests and 3 lifts.
Initially, at t = 0, lift #1 will be at floor #2 whereas lift #2 and #3 will be at floor#5 (Initial allocation).
Request #1, #4, #5 can be responded instantly, i.e. waiting time = 0.
Lift #1 will get unallocated at floor 3 at time t = 1.
Lift #2 will get unallocated at floor 7 at time t = 2 + 2 = 4.
Lift #3 will get unallocated at floor 6 at time t = 3 + 1 = 4.
Request #2 can be served by lift #1. Waiting time would be 2 - 1 = 1.
Now, lift #1 will get unallocated at floor #5 at time t = 4 + 1 + 3 = 8.
Request #3 can be served by lift #3 as it will be floor #6 at t = 4. Waiting time = 0.
Waiting time of all requests - {0, 1, 0, 0, 0}.
Therefore, the output is 1.
We are reviewing the answer, please check after sometimes
Recommended Codevita Problems
Count Pairs | 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
Number Distancing | TCS CodeVita 9 Solution ( Zone 1 ) 2020
Railway Station | TCS CodeVita 9 Solution ( Zone 1 ) 2020
