TopCoder problem "SmartElevator" used in SRM 156 (Division I Level Two)



Problem Statement

    

You have been put in charge of writing the sofware that powers an elevator in a very tall office building. Because there is only one elevator in the building, and many floors, the designers of the elevator gave it the capacity to remember past usage history. By assuming that the employees will probably use the elevator in the same ways and at the same times each day (arriving at work, going to the cafeteria, leaving for the day), the software can be a much better judge of where to travel and when. For example, if it's currently on the fifth floor, and it knows that the next employee to use the elevator will be on the third floor, it can travel there early so that the employee will not have to spend any time waiting.

Given the arrival times, starting floors, and destination floors of each employee for the day, determine the fastest time in which the elevator can get each employee to his or her destination. The elevator starts on floor 1 at time 0. Travelling from floor p to floor q takes (abs(p - q)) units of time. Also, the elevator may stand still for any length of time, if that is optimal. Assume that it takes no time for employees to enter or exit the elevator. Your method should return the minimal value of T such that, at time T, all employees have arrived at their destinations. Employee i corresponds to the ith element of each input parameter.

 

Definition

    
Class:SmartElevator
Method:timeWaiting
Parameters:int[], int[], int[]
Returns:int
Method signature:int timeWaiting(int[] arrivalTime, int[] startingFloor, int[] destinationFloor)
(be sure your method is public)
    
 

Constraints

-arrivalTime will contain between 1 and 5 elements, inclusive.
-arrivalTime, startingFloor, and destinationFloor will all contain the same number of elements.
-Each element in arrivalTime will be between 1 and 1000000, inclusive.
-Each element in startingFloor will be between 1 and 1000000, inclusive.
-Each element in destinationFloor will be between 1 and 1000000, inclusive.
-For all valid i, startingFloor[i] will never be equal to destinationFloor[i].
 

Examples

0)
    
{5}
{30}
{50}
Returns: 49

In this example, there is only one passenger. He will arrive on floor 30 at time 5, but the elevator will not be able to get to floor 30 until time 29. It will then pick up the employee and drop him off at floor 50 at time 49.

1)
    
{100}
{30}
{50}
Returns: 120

This is the same as example 0, but now the elevator can be ready at floor 30 when the employee arrives at time 100. It will still take 20 units of time to reach floor 50, dropping off the passenger at time 120.

2)
    
{10,120}
{1,100}
{210,200}
Returns: 230

The first employee will be picked up at time 10 on floor 1. At time 109, the elevator will arrive at floor 100. Here, it will wait 11 units of time until the second employee arrives and gets on (at time 120). It will then take another 100 units of time to reach floor 200 to drop off the second employee, and at time 230 it will finally arrive at floor 210 to drop off the first employee.

3)
    
{10,500}
{1,100}
{210,200}
Returns: 600

This is the same as example 2, but now the second employee doesn't arrive until time 500. In this case, it makes more sense for the elevator to drop the first employee off immedately, and then return to floor 100 to wait for the second employee.

4)
    
{1000,1200,1600,2000,2400}
{500,500,500,500,500}
{700,300,700,300,700}
Returns: 2600

The elevator should wait at floor 500 until time 2000, picking up the first four passengers as they arrive. It should drop off the second and fourth employees on floor 300, then return to floor 500 to pick up the fifth employee, and finally drop off the first, third, and fifth employees on floor 700.

5)
    
{775397,261225,870141,287698,884334}
{82225,958610,998971,413596,21922}
{769962,78706,477861,237168,258488}
Returns: 2724059

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1788

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4585&pm=1788

Writer:

LunaticFringe

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force