CODEVITA (TCS)
 |
TCS CodeVita
CodeVita Round 1 2020 question Season 9
CodeVita :
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.
0 <= S, D <= 100.
1 <= N, M <= 1000.
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.
3 2
0 2 3
4 2 5
6 7 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.
5 3
0 2 3
4 2 5
6 7 3
3 5 6
2 5 7
- 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.
0 Comments