FastPrep
Problem · Array

Time-Ordered Elevator Dispatch

Learn this problem
● MediumPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

You are given the starting floors of several elevators and a time-ordered sequence of passenger events. Every elevator starts idle. Passenger i appears at floor requestFloors[i], requests direction requestDirections[i], and is processed at absolute time requestTimes[i]. Direction 1 means up and -1 means down.

Process passengers in input order. Before processing each passenger, advance every moving elevator by one integer floor per unit of elapsed time in its current direction. Idle elevators stay at their current floors. The floor line has no endpoints.

An elevator is eligible under these rules:

  • An idle elevator is always eligible.
  • An elevator moving up is eligible only when the passenger also requests up and the passenger floor is at or above the elevator's current floor.
  • An elevator moving down is eligible only when the passenger also requests down and the passenger floor is at or below the elevator's current floor.

Assign the nearest eligible elevator by absolute floor distance. If several eligible elevators are equally near, choose the smaller original index. If no elevator is eligible, the passenger is unserved and the ordinary time advance is the only state change.

After an assignment, reset the selected elevator's modeled floor to the passenger's origin and set its direction to the passenger's requested direction. Travel to the pickup is outside this simulation and consumes no simulated time. The elevator continues in that direction until a later assignment changes it. Passengers with equal times are processed in input order.

Return the index of the elevator assigned to the final passenger, or -1 if the final passenger is unserved.

Function

dispatchFinalPassenger(elevatorFloors: int[], requestFloors: int[], requestDirections: int[], requestTimes: int[]) → int

Examples

Example 1

elevatorFloors = [0,10]requestFloors = [2,8,6]requestDirections = [1,-1,-1]requestTimes = [0,2,4]return = 1

At time 0, elevator 0 is closest to floor 2, so it is assigned and begins moving up from floor 2. At time 2 it has reached floor 4, but it is ineligible for a down request. Idle elevator 1 is assigned at floor 8 and begins moving down. At time 4 both elevators are at floor 6, but only elevator 1 matches the final down request, so the result is 1.

Example 2

elevatorFloors = [0,10,20]requestFloors = [5,15]requestDirections = [1,1]requestTimes = [0,0]return = 1

The first request is equally distant from elevators 0 and 1, so index 0 wins. No time elapses before the second request. Elevators 1 and 2 are both five floors away and idle, so the smaller index 1 serves the final passenger.

Example 3

elevatorFloors = [0]requestFloors = [0,-1]requestDirections = [1,-1]requestTimes = [0,1]return = -1

Elevator 0 accepts the first up request. By time 1 it is at floor 1 and still moving up, so it is ineligible for the final down request at floor -1. The final passenger is unserved.

Constraints

  • 1 <= elevatorFloors.length <= 200
  • 1 <= requestFloors.length <= 2000
  • requestDirections.length == requestFloors.length
  • requestTimes.length == requestFloors.length
  • -10^6 <= elevatorFloors[i], requestFloors[i] <= 10^6
  • requestDirections[i] is either -1 or 1.
  • 0 <= requestTimes[i] <= 10^9
  • requestTimes is nondecreasing.

More Pinterest problems

drafts saved locally
public int dispatchFinalPassenger(int[] elevatorFloors, int[] requestFloors, int[] requestDirections, int[] requestTimes) {
    // write your code here
}
elevatorFloors[0,10]
requestFloors[2,8,6]
requestDirections[1,-1,-1]
requestTimes[0,2,4]
expected1
checking account