Accessible Lift Dispatcher
Problem
A hospital operates several lift cars, but not every car serves every floor or supports passengers who need an accessible car. The control system must reserve enough capacity before pickup and must continue to make sensible choices as cars move, open their doors, or go out of service.
Design AccessibleLiftDispatcher, an in-memory controller that assigns each origin-and-destination request to an eligible car. The dispatcher also processes the ordered sensor events that move a request from waiting to pickup and finally to completion.
Requirements
- Request lifecycle. A valid request starts pending, may be assigned to one car, becomes picked up when that car opens at its origin, and completes when the car later opens at its destination.
- Accessibility and eligibility. Accessible requests are considered before standard requests and may use only accessible cars. Any assigned car must be available, have closed doors, serve both endpoints, and have enough unreserved capacity. Standard requests may use either kind of car.
- Deterministic dispatch. One
dispatchNextcall assigns at most one request. Pending requests are considered by request type, with accessible first, then by ascending request ID. A request with no eligible car is skipped. Eligible cars are ordered by lower reserved passenger count, then shorter distance to the request origin, then ASCII car ID. - Capacity reservation. Assignment reserves the full passenger count until completion or reassignment. Waiting and picked-up requests both count toward the reservation, which stays between zero and car capacity.
- Stable stops. An idle car targets the assigned request's origin. More assignments do not change an existing target. After a target is serviced, the next required stop is the nearest to the current floor, with the lower floor winning a distance tie.
- Sensor events. A car may move only while available with closed doors, exactly one floor toward a different current target. Its doors may open only while available and closed at the target, and may close only while open.
- Door processing. Opening completes picked-up requests at the floor before picking up waiting requests there. Each result list is in ascending request-ID order, then the car selects its next target. Closing changes no request and returns two empty lists.
- Availability. A car may be disabled only while available with closed doors and no picked-up requests. Its waiting assignments return to pending, its reservation becomes zero, and its target is cleared. Enabling an unavailable car preserves its floor and restores it with closed doors, no target, and no reservation.
- Inspection. Pending IDs follow dispatch consideration order. Active assignments are ordered by request ID and have phase
"assigned"or"picked-up". Requeued IDs are ascending. Returned records and arrays are detached snapshots. - Failure atomicity. Invalid arguments raise
ArgumentError, unknown cars raiseUnknownCarError, and invalid state transitions raiseStateError. A rejected call changes no dispatcher state.
API
The starter template supplies these public value types:
| Type | Fields |
|---|---|
CarSpec | carId: string, initialFloor: integer, capacity: integer, accessible: boolean, serviceFloors: integer[] |
Assignment | requestId: integer, carId: string, phase: string |
DoorEventResult | completedRequestIds: integer[], pickedUpRequestIds: integer[] |
| Signature | Returns | Behavior |
|---|---|---|
AccessibleLiftDispatcher(minFloor: integer, maxFloor: integer, cars: CarSpec[]) | Not applicable | Creates copied car state with closed doors, available status, zero reservation, and no target. Invalid building or car data raises ArgumentError. |
requestLift(originFloor: integer, destinationFloor: integer, passengerCount: integer, requestType: string) | integer | Creates a pending request and returns the next ID, starting at 1. The type must be "standard" or "accessible". Invalid arguments raise ArgumentError; a request that is too large for every eligible car remains valid and pending. |
dispatchNext() | Assignment? | Assigns the first serviceable pending request to its highest-ranked eligible car. Returns no value without changing state if none is serviceable. |
reportCarFloor(carId: string, floor: integer) | void | Records one valid movement step. An unknown car raises UnknownCarError; invalid movement raises StateError. |
reportDoor(carId: string, doorState: string) | DoorEventResult | Reports "open" or "closed" and applies the door rules. An invalid string raises ArgumentError; an unknown car or invalid transition raises the corresponding failure. |
setCarAvailable(carId: string, available: boolean) | integer[] | Changes availability. Disabling returns requeued IDs; enabling returns an empty array. Repeating the current value or disabling an ineligible car raises StateError. |
getPendingRequests() | integer[] | Returns pending request IDs in dispatch consideration order. |
getAssignments() | Assignment[] | Returns assigned and picked-up requests in ascending request-ID order. |
getNextStop(carId: string) | integer? | Returns the stable target, including the current floor when the doors must open there, or no value if no work remains. An unknown car raises UnknownCarError. |
Constructor data is valid only when minFloor < maxFloor, there are 1 through 20 cars, and every initial floor is in the building. Each unique car ID must match [A-Za-z0-9-]{1,32}. Capacity is 1 through 1000. Each service-floor list is non-empty, has no duplicates, stays within the building, and includes the initial floor.
Request floors must be inside the building and differ. Passenger count is 1 through 1000. All public strings, arrays, records, and record fields are non-null. Testcases do not pass null values; null input behavior is outside this public contract.
The language-specific failure mappings are:
| Failure | Python 3.12 | Java 21 | C++ 20 |
|---|---|---|---|
ArgumentError | ValueError | IllegalArgumentException | std::invalid_argument |
UnknownCarError | KeyError | NoSuchElementException | std::out_of_range |
StateError | RuntimeError | IllegalStateException | std::logic_error |
Examples
Given an accessible car A at floor 0, capacity 3, serving floors 0 through 4:
| Step | Operation | Result |
|---|---|---|
| 1 | requestLift(2, 4, 2, "standard") | 1 |
| 2 | dispatchNext() | Assignment(1, "A", "assigned") |
| 3 | Move to floors 1 and 2, then reportDoor("A", "open") | DoorEventResult([], [1]) |
| 4 | getAssignments() | [Assignment(1, "A", "picked-up")] |
| 5 | Close, move to floors 3 and 4, then open | DoorEventResult([1], []) |
| 6 | getNextStop("A") | No value |
Constraints
- Building floors are integers from
-1000through1000. - A dispatcher has 1 through 20 cars, and each car serves at most 2001 floors.
- At most 1000 requests and 10000 total public method calls occur in one testcase.
- All passenger, capacity, reservation, distance, and request-ID calculations fit in signed 32-bit integers and never become negative.
- Car IDs contain only ASCII characters, so lexicographic ordering is the same in every runtime.
Notes
All calls form one ordered simulation stream. Methods are non-blocking, and concurrent calls to one dispatcher instance are out of scope. Testcases use one thread; actions within that thread run in order.