How to design an elevator system

In this lesson, we’ll design an elevator control system for a 20-floor building. By the end you’ll be able to name the scheduling algorithm that keeps anyone from waiting forever, prove why it does, and defend which decision belongs in which object.

The problem has two halves.

The first is the object model: the classes and their relationships. The objects are simple. A building has cars, a car has a position and a door, a floor has two buttons. Drawing that model is quick, and it is not the hard part.

The second half is the scheduler: the rule that decides the order in which one car serves its waiting passengers. That is where the design lives. We name the algorithm (LOOK), work one burst of calls through it by hand, show why nobody waits forever under it and the one implementation detail that guarantee rests on, and explain which classes exist because they are expected to change.

Three design patterns appear here, each defined again where it arrives:

Strategy: a policy in its own object, swappable without editing the caller.
State: one named situation an object can be in, together with the rules that apply while it is there.
Command: a request turned into an object you can queue, log and replay.

The pattern vocabulary is treated on its own in OOP fundamentals, and the Strategy argument returns in its most common industrial form in the grocery store lesson. Neither is needed to follow this page.

What goes in, and what comes out

Fix the shape of the problem before drawing a single class. The system takes two kinds of request and produces two kinds of answer.

IN   a hall call    someone at floor 15 pressing the DOWN button
                    -> HallCall(floor=15, direction=Direction.DOWN)
IN   a car call     someone inside car 1 pressing "6"
                    -> CarCall(floor=6)

OUT  an assignment  which car answers a given hall call
                    -> car #2
OUT  a stop order   the sequence of floors one car visits, and its cost
                    -> [3, 6, 18, 15, 11], costing 24 floors of travel

The two outputs are two different decisions made by two different objects.

flowchart TD
    HC["Hall call: floor + direction"] --> D["Dispatcher: which car answers"]
    D --> C["ElevatorCar"]
    CC["Car call: floor"] --> C
    C --> S["Sweep order: what floors, in what order"]

Choosing which car answers a hall call is the dispatcher’s job. It is a policy, and policies change. Choosing what order one car serves the calls it already holds is the car’s job. It is an algorithm, and this one does not change. Keeping those two decisions in separate objects is the structural choice the whole design rests on.

Variations that change the model

Four questions decide which classes exist at all. Each one flips a class in or out, which is why they come before the diagram.

Question	If yes	If no
One car or a bank?	You need a `Dispatcher` and a dispatch policy	A single car’s queue, half the design
Destination-dispatch lobby, or up/down buttons?	Passengers declare a floor before boarding; hall calls carry a target and you can group by destination	Hall calls carry only a direction, and the car cannot know load until the doors close
Are cars homogeneous?	One policy	Express cars, freight cars, capacity limits, so the policy must be able to refuse a car
What is being optimized?	Total travel, mean wait and p99 wait are three objectives that pick three different policies	Default to mean wait with a bounded worst case

Three terms in that table need unpacking:

Destination dispatch is the lobby arrangement where you key in your floor at a panel outside the elevators and a screen tells you which car to board, instead of pressing a plain up or down button. The controller therefore knows your destination before you are inside the car.
Mean wait is the average time a passenger stands in the hallway. p99 wait is the 99th percentile of that same wait: the number 99 out of 100 passengers come in under, or how bad it gets for the unluckiest one percent. The two conflict as objectives. A policy that improves one usually worsens the other, which is why “what is being optimized?” is a real question.

The second row matters most. Up/down buttons is the classic version and the harder scheduling problem, because the controller has strictly less information. Assume it unless told otherwise.

Actors and events

Five parties send events into this system.

Actor	Action	What it produces
Passenger, in the hallway	presses UP or DOWN at floor `f`	a hall call
Passenger, inside a car	presses a destination floor	a car call
Passenger, at the doors	blocks the door, or presses open	a door state change
Maintenance technician	takes a car out of service	a service-mode change
Fire panel	recalls every car to the lobby	a priority override

Two of these carry the rest of the lesson. A hall call is a request from outside a car: someone at a floor wanting to travel in a direction. A car call is a request from inside a car: someone already aboard wanting off at a floor. They are two different request kinds and, as the next section argues, two different types.

The fire panel is worth noticing even though the design does not build it. A recall is not a request that joins the queue; it cancels everything and drives every car to the lobby regardless of what each was doing. That is a mode, not an event, and a flat set of states cannot express it cleanly. More on that under the state-machine assumptions below.

Core objects, and why those

Five objects carry the design. For each, what matters is not what it does but which tempting alternative it beats.

Object	Responsibility	Why not the obvious alternative
`HallCall(floor, direction)`	A person waiting at a floor wanting to go a direction	A plain `Request(floor)` loses the direction, and direction is exactly what LOOK needs to decide whether a passing car should stop
`CarCall(floor)`	A person inside a car wanting off	Has no direction, because it is implied by where the car already is
`ElevatorCar`	Position, motion, door, its own pending set	Not “Elevator + Controller + Motor”: the motor is a driver, not a domain object
`Dispatcher`	Assigns a hall call to a car	“Each car decides for itself” is a distributed-consensus problem for zero benefit
`DispatchStrategy`	The policy, swappable	See the Strategy decision below

Distributed consensus in row four means several independent parties agreeing on one answer with no central authority, over a channel where messages can be delayed or lost. It is a famously hard problem, and there is nothing to gain from creating one inside a building where a single controller can simply decide.

A Floor class with a list of waiting passengers is the classic over-model. A floor has no behaviour: it is an integer plus, at most, two booleans for the lit up and down buttons. Keep the floor as an int and track those two booleans in the dispatcher’s set of unanswered hall calls. Adding a Floor object later touches one file, so there is no cost to leaving it out now.

Class diagram

The whole model fits in one diagram. The arrowheads carry claims the boxes do not, so each line is read back as an English sentence below.

Two things in the diagram are model-only and are not in the running code further down: the Building class and Dispatcher.step(). The code implements the requests, one car’s sweep, Dispatcher.assign and the strategies, and stops there.

classDiagram
    class Building {
        +int floors
        +request(call)
    }
    class Dispatcher {
        +assign(HallCall) ElevatorCar
        +step()
    }
    class ElevatorCar {
        +int id
        +int position
        +Direction heading
        +DoorState door
        +accept(Request)
        +peek_next_stop() int
        +advance_to_next_stop() int
    }
    class Request {
        +int floor
    }
    class HallCall {
        +Direction direction
    }
    class CarCall
    class DispatchStrategy {
        <<interface>>
        +choose(cars, call) ElevatorCar
    }
    class NearestCarStrategy
    class LookCostStrategy
    class FairnessStrategy

    Building "1" *-- "1..*" ElevatorCar : owns lifetime
    Building "1" *-- "1" Dispatcher
    Dispatcher "1" o-- "1..*" ElevatorCar : schedules, does not own
    Dispatcher "1" --> "1" DispatchStrategy : delegates policy
    ElevatorCar "1" o-- "0..*" Request : pending
    Request <|-- HallCall
    Request <|-- CarCall
    DispatchStrategy <|.. NearestCarStrategy
    DispatchStrategy <|.. LookCostStrategy
    DispatchStrategy .. FairnessStrategy : wants to, but widens choose()

Reading the notation

This is a UML class diagram (UML, the Unified Modeling Language, is the standard set of shapes for drawing software structure). Each box is a class; the lines inside are its fields and methods, and a leading + means public. <<interface>> marks a class that is only a promise of methods with no implementation of its own.

The quoted numbers at a line’s ends are multiplicities: 1 is exactly one, 1..* is one or more, 0..* is any number including none.

Six line styles appear, each meaning something different:

*--, a filled diamond, is composition: the owner controls the part’s lifetime. Destroy the owner and the part goes too.
o--, a hollow diamond, is aggregation: a “has a” that does not control lifetime, so the part can outlive the whole or be shared.
-->, an open arrow, is association: the tail holds a reference to the head, and claims nothing more.
<|--, a hollow triangle on a solid line, is inheritance: the tail is a kind of the head.
<|.., the same triangle on a dashed line, is realization: the tail implements the interface without inheriting any code.
.., a dashed line with no arrowhead, is a plain link: the two classes are related and the label says how.

Read as sentences:

Building *-- ElevatorCar (owns lifetime): a building composes one or more cars. Demolish it and the cars go with it.
Building *-- Dispatcher: a building composes exactly one dispatcher.
Dispatcher o-- ElevatorCar (schedules, does not own): the dispatcher aggregates those same cars, so replacing the dispatcher leaves every car running.
Dispatcher --> DispatchStrategy (delegates policy): the dispatcher holds a reference to one strategy it merely uses, hence a plain association.
ElevatorCar o-- Request (pending): each car aggregates any number of requests as its outstanding work.
Request <|-- HallCall and Request <|-- CarCall: both call kinds are kinds of Request, which is what lets a car hold either one in the same pending set.
DispatchStrategy <|.. NearestCarStrategy and <|.. LookCostStrategy: each realizes the interface, which is what lets the dispatcher hold either without knowing which.
DispatchStrategy .. FairnessStrategy: a plain link, not a realization. It does the same job, but its choose takes an extra argument, so it does not satisfy the interface. Drawing a realization arrow there would make the diagram lie about a class that genuinely does not fit; the honest repair is in the fairness extension below.

The two arrows into ElevatorCar differ for a reason: the building composes its cars while the dispatcher aggregates them. Getting that pair backwards says the wrong thing about what happens when you swap a controller.

What this class structure assumes

A class diagram is a frozen bet about what will change. Every interface says “I expect this to vary”. Every hard-coded field says “I expect this to hold forever”. Naming those bets is the transferable skill; the specific elevator is not.

Assumed to vary, and therefore given an interface or a parameter. The third column is the cost of having bet wrong, which is what makes each row a decision and not a habit.

What varies	How the design absorbs it	Cost of getting it wrong
Which car answers a hall call	`DispatchStrategy`, an interface with one method	A `switch` inside `Dispatcher`, edited for every new policy
Which floors a car may serve	A `serves` set on the car, consulted by `can_serve`	Express cars become a special case inside every strategy
Whether a car is available	An `in_service` flag, consulted by the same predicate	A separate list of active cars, which drifts from reality
The number of cars and floors	Constructor arguments	A twenty-floor constant compiled into the scheduler
The objective being optimized	Which strategy you install	Mean wait and worst-case wait cannot both be tuned

Assumed fixed, and therefore baked into the structure. The largest one is deliberate: the per-car stop ordering is not swappable. LOOK is written directly into ElevatorCar.advance_to_next_stop, while dispatch is an interface. That asymmetry is a claim that dispatch policy is what a building owner argues about while sweep order is settled engineering. It is a reasonable bet, and if it were wrong the fix is a second Strategy interface on the car.

Five smaller fixed bets sit underneath it:

One dispatcher, and it is the sole authority. Cars never negotiate with each other.
A call is assigned to exactly one car the moment it arrives, and never reassigned. That is why the pending set lives on the car, not the dispatcher.
A car’s plan is a set of floors, not a timed schedule. Door dwell, acceleration and loading do not exist in the model.
Position is an integer floor, not a continuous height.
Every car runs in its own shaft, so two cars can never collide.

What a state machine assumes

A state machine is an object always in exactly one of a fixed set of named situations, with defined rules for moving between them. The car is described further down as a small one, moving between IDLE, MOVING and DOORS_OPEN. Every state machine rests on two assumptions, and this design quietly violates both:

The set of states is closed and known at design time. Naming three states claims the car is never in a fourth. It is: doors obstructed, releveling at a floor, emergency stop, and fire recall. Fire recall is the instructive one, because it is not reachable by any normal event from any normal state. It preempts whatever the car was doing, and a flat set of states cannot express “drop everything and do this instead” without adding an edge from every state to the new one. The honest structures are a hierarchical state machine, where a high-priority parent mode overrides its children, or a separate mode flag consulted before the state machine runs at all. Ignore this and a recall arriving during DOORS_OPEN has no defined transition, so the car finishes its trip during a fire.
Transitions are total: every combination of state and event has a defined outcome. This design does not achieve that. advance_to_next_stop() and arrive() never inspect the car’s state; arrive sets the door to OPEN unconditionally, nothing ever closes it, and door is written but never read. The code is a scheduler, not a door controller. That is a scope decision, not an oversight. The vending machine lesson shows the contrast: a machine where every undefined combination inherits an explicit refusal instead of quietly doing something.

What a different question would have produced

Four rewrites of the problem, and what each does to the class model:

Destination dispatch collapses HallCall and CarCall into one request carrying origin and destination, makes the direction filter LOOK depends on unnecessary, and lets the dispatcher group passengers going to the same floor into one car: a different and easier optimization.
Revocable assignments mean the pending set cannot live on the car, because the dispatcher must move calls between cars as conditions change. Ownership of every unserved call migrates to the dispatcher and each car is handed only its next stop. That is what real high-traffic controllers do, and it costs the clean per-car queue that makes this design testable.
Two cars sharing one shaft (real, in tall buildings) kills the independence assumption. Each car’s plan constrains its neighbour’s, cars can deadlock needing to pass each other, and per-car LOOK is no longer well defined.
Optimizing p99 wait instead of total travel makes LookCostStrategy the wrong default and the fairness policy below the right one. Same classes, different installed policy, which is the payoff of having made dispatch an interface.

The scheduler: LOOK, not FCFS

Name the algorithm, then run one concrete burst of calls through both it and the naive alternative.

FCFS, first-come first-served, is the naive rule: serve requests in the order they were pressed.

LOOK is the good rule. The car sweeps in one direction as far as the furthest request that way, serving everything on the path, then reverses and does the same going back. It is called LOOK because before reversing it looks ahead to see whether anything is still pending in the current direction. Its cruder relative SCAN always runs to the physical top or bottom before turning, wasting the empty end of every sweep. Both names come from disk-drive head scheduling, where the identical problem is ordering reads across a spinning platter.

One burst, worked by hand

Take a 20-floor building, one car parked at floor 1, and five hall calls arriving in this order:

#1  floor 15  DOWN
#2  floor  3  UP
#3  floor 18  UP
#4  floor  6  UP
#5  floor 11  DOWN

FCFS serves them in arrival order: 1 -> 15 -> 3 -> 18 -> 6 -> 11. Summing the gaps between consecutive stops (14 + 12 + 15 + 12 + 5) gives 58 floors of travel, most of it doubling back.

LOOK sweeps up to the highest pending request serving every UP call, then reverses and serves the DOWN calls descending: 1 -> 3 -> 6 -> 18 -> 15 -> 11. Because the path never doubles back, its cost is just the two sweep lengths: up 17 (floor 1 to 18) plus down 7 (floor 18 to 11), which is 24 floors.

flowchart TD
    subgraph FCFS["FCFS: 58 floors, doubles back"]
        F1["1"] --> F2["15"] --> F3["3"] --> F4["18"] --> F5["6"] --> F6["11"]
    end
    subgraph LOOK["LOOK: 24 floors, one up-sweep then one down-sweep"]
        L1["1"] --> L2["3"] --> L3["6"] --> L4["18"] --> L5["15"] --> L6["11"]
    end

Same five passengers, 58 floors versus 24, 59% less travel from service order alone. That is why the algorithm exists.

Why the gap widens with load

One example is an anecdote. It becomes a rule once you ask what each policy costs per request as the building gets busier.

FCFS travel per request does not depend on how many requests are pending: it always flies from wherever it is to wherever the next-pressed button happens to be. If two floors are drawn independently and uniformly at random from 1..n, the expected distance between them is (n^2 - 1) / (3n), which for n = 20 is about 6.65 floors per request, forever.

A full LOOK sweep costs 2(n-1) = 38 floors (up the building and back) but serves every pending request in one pass, so with m requests pending it costs 38 / m per request. The two break even near 38 / 6.65, about 6 concurrent requests. Above that LOOK wins, and its per-request cost keeps falling while FCFS stays flat. The busier the building, the worse FCFS is, which is precisely the regime you built an elevator for.

That crossover is conservative: 6.65 is FCFS’s expected cost while 38 is LOOK’s worst case (a sweep that turns below the top floor is shorter), so the real crossover is a little lower.

The starvation is in the other naive policy

To starve a request is to leave it unserved indefinitely while newer requests keep overtaking it.

FCFS is first-in, first-out, so it does not starve anyone. It is merely slow. The policy that starves is the greedy one people reach for instead: nearest-request-first, known in disk scheduling as SSTF (shortest seek time first). Here is the sequence that kills it:

car idle at floor 1, one pending call at floor 20
lobby traffic arrives at floors 2, 3, 4 every few seconds
nearest-first picks a lobby floor every single time
floor 20 waits forever

LOOK fixes that, and the fix is provable: a request is served within one full sweep, so worst-case wait is bounded by 2(n-1) = 38 floors of travel plus the door time of the stops in between. SSTF has no such bound.

That proof has a precondition, and it is the one implementations get wrong. A sweep is bounded only if the set of calls it will serve is fixed when the sweep begins. Recompute the furthest pending stop on every step (the natural way to write it) and a steady stream of requests in the current direction extends the sweep forever, so the far end starves exactly the way SSTF does. That is what the frozen sweep_target field in the code exists for, and the 500-tick assertion beside it turns the bound from a claim into a test.

LOOK does have a bad case: for a single request on an idle car it is worse than SSTF, because a call one floor behind the car waits for the sweep to turn around instead of being picked up immediately. Real controllers cheat here: if the car is idle with an empty queue, take the nearest call and start the sweep from there.

The request model, and Command

Two questions hang over the request model: why the two request kinds are separate types, and what turning requests into objects at all buys and costs.

Why two request types instead of one

HallCall and CarCall are separate types because the sweep filter treats them differently. On an up-sweep a car stops for every CarCall on its path, because someone aboard wants off and there is no direction to check. It stops for a HallCall only when that call’s direction is UP, because a down-bound passenger who boards an up-going car rides the wrong way.

Collapse both into one Request(floor) and you are forced into a direction: Optional[Direction] field (Optional[T] being the type “either a T or nothing”) plus a None check at every stop decision. That is the same two-case split, with worse names.

Requests as Command objects

A request object is also the natural Command: the pattern turns a request into an object carrying everything needed to service it, which makes it queueable, loggable and replayable. Two things fall out of that.

The first is an audit log, a durable record of what was asked and what was done, so you can answer “why did car 2 skip floor 9 at 09:14?” The second is deterministic replay: replaying the same recorded requests must produce the same stops every time, which is what makes the simulator testable.

The cost is memory. A press(5) call now allocates an object, and the queue holds objects instead of an int bitmask (a single integer whose bits stand for floors, so a 200-floor building’s entire pending set fits in 200 bits, about 50 bytes). Each Command object costs an allocation and a few dozen bytes per press. In a real controller you would keep the bitmask for scheduling and keep the Command objects only in the log.

Dispatch is a Strategy

With one car there is no dispatch. With a bank of six, choosing which car answers a hall call is a separate policy from how each car orders its own stops, and it is the one a building operator changes.

The diagram below is the strategy corner of the class diagram on its own. The label on each line names the quantity that implementation minimizes; the three different quantities are the argument for having an interface at all.

classDiagram
    class Dispatcher
    class DispatchStrategy {
        <<interface>>
        +choose(cars, call)
    }
    Dispatcher --> DispatchStrategy
    DispatchStrategy <|.. NearestCarStrategy : min distance
    DispatchStrategy <|.. LookCostStrategy : min added sweep
    DispatchStrategy .. FairnessStrategy : min max-wait, wider signature

NearestCarStrategy minimizes distance: the car with the smallest gap between its position and the calling floor.
LookCostStrategy minimizes added sweep: the car whose route grows least when this call is added. The code approximates that as distance + penalty x stops already queued instead of re-simulating each car’s sweep, which is cheaper and good enough.
FairnessStrategy minimizes the max wait: the assignment producing the smallest worst wait, not the smallest average. It hangs off a plain link instead of a realization arrow because its choose takes one extra argument, so it does not fit the interface.

A pattern is worth its cost when you can name the second and third implementation, and here all three are named.

What Strategy makes cheap: the three extensions at the end of this lesson are each one new class and zero edits to Dispatcher or ElevatorCar. What it costs: you can no longer read the dispatch decision by reading Dispatcher. The flow now goes Dispatcher -> DispatchStrategy -> concrete class, three files for what a switch would say in twelve lines. That readability tax is worth paying only because dispatch policy is the thing that provably changes. Door timing is not, so do not make it a Strategy too.

Working Python

The design as running code, in three parts:

The request types and the two travel costs: the 58-versus-24 arithmetic as executable assertions.
One car’s LOOK sweep: ElevatorCar, and the two details that separate real LOOK from something that resembles it.
The dispatcher and its swappable policy: Dispatcher plus two strategies that give different answers to the same call.

Every block runs on its own, and the blocks also run in sequence.

Part 1 — the request types and the two travel costs

This block defines the two call types and two functions that price a set of calls, one per rule. The assertions at the bottom are the hand calculation, checked by the interpreter.

from __future__ import annotations

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from enum import Enum
from typing import List, Optional, Sequence, Set, Union


class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0


@dataclass(frozen=True)
class HallCall:
    """Someone waiting at a floor. Carries the direction they want to go."""
    floor: int
    direction: Direction


@dataclass(frozen=True)
class CarCall:
    """Someone inside a car. Direction is implied by where the car is."""
    floor: int


Request = Union[HallCall, CarCall]


def fcfs_travel(start: int, reqs: Sequence[Request]) -> int:
    pos, dist = start, 0
    for r in reqs:
        dist += abs(r.floor - pos)
        pos = r.floor
    return dist


def look_travel(start: int, reqs: Sequence[Request]) -> int:
    """Sweep up serving UP + car calls, reverse, serve DOWN calls descending."""
    up = sorted({r.floor for r in reqs
                 if isinstance(r, CarCall) or r.direction is Direction.UP})
    down = sorted({r.floor for r in reqs
                   if isinstance(r, HallCall) and r.direction is Direction.DOWN},
                  reverse=True)
    pos, dist = start, 0
    for f in [f for f in up if f >= start] + down + [f for f in up if f < start]:
        dist += abs(f - pos)
        pos = f
    return dist


BURST: List[Request] = [
    HallCall(15, Direction.DOWN),
    HallCall(3, Direction.UP),
    HallCall(18, Direction.UP),
    HallCall(6, Direction.UP),
    HallCall(11, Direction.DOWN),
]

assert fcfs_travel(1, BURST) == 58
assert look_travel(1, BURST) == 24
assert fcfs_travel(1, BURST) - look_travel(1, BURST) == 34

# A CarCall has no direction, so it rides whichever sweep reaches it. One at
# floor 9 is free here: the up-sweep already passes through 9 on its way to 18.
assert look_travel(1, BURST + [CarCall(9)]) == 24
# FCFS pays for it, because it flies back down to 9 after finishing at 11.
assert fcfs_travel(1, BURST + [CarCall(9)]) == 60

Four Python idioms are doing work here.

class Direction(Enum) defines an enumeration, a closed set of named constants. Direction.UP is a distinct object you compare with is, not a string somebody can typo. Giving UP the value 1 and DOWN the value -1 means the direction doubles as the sign of the car’s motion.
@dataclass(frozen=True) generates the constructor, printable representation and equality from the fields. frozen=True makes instances immutable and therefore hashable, so a call can go in a set and be deduplicated.
Request = Union[HallCall, CarCall] names a type that is either kind: the type-level statement of “two request kinds, one pending queue”.
from __future__ import annotations stores annotations as text instead of evaluating them, so newer type syntax runs on older interpreters.

The last two assertions add a CarCall at floor 9 to the burst: LOOK still costs 24 because its up-sweep already passes floor 9, while FCFS climbs to 60 because it flies back down to 9 after finishing at 11.

One thing before moving on: look_travel is a costing function, not the car. It prices a whole batch of calls in one shot and is deliberately the shortest code that produces the 24. The real per-call LOOK a car runs is Part 2, and it handles cases this function does not: an idle car with no heading, calls arriving mid-sweep, and the reversal itself.

Part 2 — one car’s LOOK sweep

The car is a small State machine (IDLE -> MOVING -> DOORS_OPEN -> IDLE) but it is described, not implemented: the code has no state field, only heading and door. It tracks the door but never acts on it. It is the scheduler, not the door controller.

Four things in ElevatorCar are worth attention:

the two stop sets, up_stops and down_stops, which make the direction filter trivial;
sweep_target, frozen at the start of a sweep and never recomputed mid-sweep;
the split between peek_next_stop (pure) and advance_to_next_stop (mutating);
the driver loop and five assertion groups, which exercise the sweep, car calls, purity, the starvation bound, and floor validation.

from __future__ import annotations

from dataclasses import dataclass, field
from enum import Enum
from typing import List, Optional, Set, Tuple, Union

# Repeated from the block above so this one runs on its own.
class Direction(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0

@dataclass(frozen=True)
class HallCall:
    floor: int
    direction: Direction

@dataclass(frozen=True)
class CarCall:
    floor: int

Request = Union[HallCall, CarCall]

class DoorState(Enum):
    CLOSED = "closed"
    OPEN = "open"

@dataclass
class ElevatorCar:
    id: int
    top_floor: int
    position: int = 1
    heading: Direction = Direction.IDLE
    door: DoorState = DoorState.CLOSED
    up_stops: Set[int] = field(default_factory=set)     # serve while heading UP
    down_stops: Set[int] = field(default_factory=set)   # serve while heading DOWN
    sweep_target: Optional[int] = None                  # frozen when a sweep starts

    def accept(self, req: Request) -> None:
        if not 1 <= req.floor <= self.top_floor:
            raise ValueError(f"floor {req.floor} outside 1..{self.top_floor}")
        if isinstance(req, CarCall):
            # a car call has no direction: it rides whichever sweep reaches it
            (self.up_stops if req.floor >= self.position
             else self.down_stops).add(req.floor)
        else:
            (self.up_stops if req.direction is Direction.UP
             else self.down_stops).add(req.floor)

    def _begin_sweep(self, direction: Direction) -> None:
        """LOOK: finish the current sweep, then reverse. `sweep_target` is fixed
        when the sweep starts. Recomputing the furthest pending stop on every
        call is what lets a stream of calls ahead of the car extend a sweep
        forever and starve the far end.
        """
        self.heading = direction
        pending = self.up_stops | self.down_stops
        ahead = [f for f in pending
                 if (f >= self.position if direction is Direction.UP
                     else f <= self.position)]
        if not ahead:
            self.sweep_target = None
        else:
            self.sweep_target = (max(ahead) if direction is Direction.UP
                                 else min(ahead))

    def peek_next_stop(self) -> Optional[int]:
        """The next stop of the sweep in progress. Pure: it changes nothing.

        `None` means *this sweep* is finished, not that the car has no work.
        """
        t = self.sweep_target
        if t is None:
            return None
        if self.heading is Direction.UP:
            ahead = [f for f in self.up_stops if self.position <= f <= t]
            return min(ahead) if ahead else (t if t > self.position else None)
        if self.heading is Direction.DOWN:
            ahead = [f for f in self.down_stops if t <= f <= self.position]
            return max(ahead) if ahead else (t if t < self.position else None)
        return None

    def _sweep_order(self) -> Tuple[Direction, ...]:
        """Reverse first. From idle, head towards the nearest call -- the cheat."""
        if self.heading is Direction.UP:
            return (Direction.DOWN, Direction.UP)
        if self.heading is Direction.DOWN:
            return (Direction.UP, Direction.DOWN)
        rest = self.up_stops | self.down_stops
        if not rest:
            return ()
        near = min(rest, key=lambda f: abs(f - self.position))
        return ((Direction.UP, Direction.DOWN) if near >= self.position
                else (Direction.DOWN, Direction.UP))

    def advance_to_next_stop(self) -> Optional[int]:
        """The next stop, starting or reversing a sweep when the current one ends.

        MUTATES: it can flip `heading` and freeze a new `sweep_target`, which
        is why the pure `peek_next_stop` exists beside it -- a dispatcher
        scoring a car must not change the car it is scoring.
        """
        stop = self.peek_next_stop()
        if stop is not None:
            return stop
        for direction in self._sweep_order():
            self._begin_sweep(direction)
            stop = self.peek_next_stop()
            if stop is not None:
                return stop
        self.heading, self.sweep_target = Direction.IDLE, None
        return None

    def arrive(self, floor: int) -> None:
        self.position = floor
        self.up_stops.discard(floor)
        self.down_stops.discard(floor)
        self.door = DoorState.OPEN
        if floor == self.sweep_target:
            self.sweep_target = None        # the frozen sweep is complete


# Drive the same five calls through the real car and check the stop order
# and the travel cost against the hand calculation.
car = ElevatorCar(id=1, top_floor=20)
for req in [HallCall(15, Direction.DOWN), HallCall(3, Direction.UP),
            HallCall(18, Direction.UP), HallCall(6, Direction.UP),
            HallCall(11, Direction.DOWN)]:
    car.accept(req)

visited, travel = [], 0
while True:
    nxt = car.advance_to_next_stop()
    if nxt is None:
        break
    travel += abs(nxt - car.position)
    car.arrive(nxt)
    visited.append(nxt)

assert visited == [3, 6, 18, 15, 11], visited
assert travel == 24, travel

# A CarCall carries no direction: it joins whichever sweep reaches it.
rider = ElevatorCar(id=2, top_floor=20, position=8)
rider.accept(CarCall(12))
rider.accept(CarCall(4))
assert rider.up_stops == {12} and rider.down_stops == {4}

# `peek` is pure: six calls, one answer, and nothing moved.
peeker = ElevatorCar(id=3, top_floor=20)
peeker.accept(HallCall(3, Direction.UP))
peeker.accept(HallCall(10, Direction.DOWN))
assert peeker.advance_to_next_stop() == 3
peeker.arrive(3)
before = (peeker.heading, peeker.position, peeker.sweep_target)
assert {peeker.peek_next_stop() for _ in range(6)} == {10}
assert (peeker.heading, peeker.position, peeker.sweep_target) == before

# The freeze is what makes the one-sweep bound true. A fresh call ahead of the
# car on every single tick cannot push the frozen turnaround further away.
starved = ElevatorCar(id=4, top_floor=20, position=1)
starved.accept(HallCall(2, Direction.DOWN))          # the victim
for tick in range(500):
    starved.accept(HallCall(20, Direction.UP))       # a new top-floor call, forever
    stop = starved.advance_to_next_stop()
    starved.arrive(stop)
    if stop == 2:
        break
assert tick == 1 and 2 not in starved.down_stops, (tick, starved.down_stops)

# The floor range is checked, so a typo cannot land in a stop set.
for bad in (HallCall(9999, Direction.UP), HallCall(-5, Direction.DOWN)):
    try:
        starved.accept(bad)
        raise AssertionError(f"{bad} accepted on a 20-floor building")
    except ValueError:
        pass

Two more idioms. field(default_factory=set) gives each car its own empty set; writing = set() would raise ValueError: mutable default … is not allowed at class-definition time, the language having closed the classic def f(x=[]) trap. Optional[int] as the return type of advance_to_next_stop says the honest thing, that sometimes there is no next stop, and the caller’s if nxt is None: break is where the sweep ends.

Where LOOK actually lives. Keeping two separate sets, up_stops and down_stops, makes the direction filter trivial: while heading up, the only candidates are stops in up_stops at or above the car, and the nearest of those is next. When nothing in up_stops remains ahead, the car still runs on to sweep_target, the turnaround floor, which may itself be a down-call. That is the case the purity assertion exercises: peeker heads UP with an empty up_stops and a sweep_target of 10, and peek_next_stop() returns 10, the floor where the DOWN call waits. After that the heading flips and the far end of the other set becomes the new target. Looking ahead before reversing is what the algorithm is named for. _sweep_order covers the idle case by starting towards the nearest pending stop in either set, the cheat mentioned above.

The two details that separate LOOK from a lookalike.

Detail one: sweep_target is frozen. _begin_sweep sets it once, and only arrive clears it, when the car actually reaches it. The set of floors this sweep will serve is decided at the start of the sweep. Recompute the furthest pending stop on every call (the version almost everyone writes) and a sweep never has a fixed end: a steady stream of calls in the current direction extends it indefinitely while the far end waits forever. The starved loop runs that scenario 500 times and terminates on the second tick. Trace it: the car starts at floor 1 holding one DOWN call at floor 2 (the victim). On tick 0 a call at floor 20 arrives, the idle car heads UP with sweep_target frozen at 20, and it runs to 20. On tick 1 another floor-20 call arrives, but it cannot move a target already reached and cleared; the car reverses, freezes sweep_target at 2, and serves the victim. Hence assert tick == 1.

Detail two: peek_next_stop is pure and advance_to_next_stop is not. A method named like a query that quietly flips the car’s heading is a trap for exactly the caller the dispatch strategy invites: a dispatcher scoring a car by where it is going next must be able to look without changing the answer. The peeker assertions call peek_next_stop() six times and check that heading, position and sweep_target all come out unchanged.

Two smaller choices in accept. accept never touches heading; only _begin_sweep and the last line of advance_to_next_stop write it, so heading cannot say UP while the car descends. That heading is not the same as the direction on the hall call: a car at floor 10 answering HallCall(5, Direction.UP) descends to 5 and then sweeps up, so its heading is DOWN for the first leg while the hall indicator correctly reads UP. accept also validates the floor against top_floor; without that check, accept(HallCall(9999, ...)) would drop 9999 into a stop set and the car would sweep forever towards a floor that does not exist.

Part 3 — the dispatcher and its swappable policy

This block is the Strategy pattern as code. The one thing to read for: Dispatcher.assign contains no policy at all, it just forwards to whatever strategy object it holds. Car here is a deliberately smaller stand-in for ElevatorCar, and the block passes the direction as the plain string "up" instead of a Direction; both points are explained after the block.

from __future__ import annotations

from abc import ABC, abstractmethod
from typing import List, Optional, Sequence

class DispatchStrategy(ABC):
    """Returns the car that should answer a hall call, or None to defer."""

    @abstractmethod
    def choose(self, cars: Sequence["Car"], floor: int,
               direction: str) -> Optional["Car"]:
        ...

class Car:                       # stand-in; the real one is above
    def __init__(self, id: int, position: int, pending: int = 0,
                 in_service: bool = True, serves=range(1, 21),
                 oldest_since: float = 0.0):
        self.id, self.position, self._pending = id, position, pending
        self.in_service, self.serves = in_service, serves
        self._oldest_since = oldest_since

    def pending(self) -> int:
        return self._pending

    def oldest_waiting_since(self) -> Optional[float]:
        """When the oldest call this car already holds was made, or None."""
        return self._oldest_since if self._pending else None

    def can_serve(self, floor: int) -> bool:
        return self.in_service and floor in self.serves

class NearestCarStrategy(DispatchStrategy):
    """Minimize distance. Simple, and starves the far end under lobby load."""

    def choose(self, cars, floor, direction):
        ok = [c for c in cars if c.can_serve(floor)]
        return min(ok, key=lambda c: abs(c.position - floor)) if ok else None

class LookCostStrategy(DispatchStrategy):
    """Minimize distance plus a penalty per stop already queued on that car."""

    def __init__(self, stop_penalty: int = 2):
        self.stop_penalty = stop_penalty

    def choose(self, cars, floor, direction):
        ok = [c for c in cars if c.can_serve(floor)]
        if not ok:
            return None
        return min(ok, key=lambda c: abs(c.position - floor)
                   + self.stop_penalty * c.pending())

class Dispatcher:
    def __init__(self, cars: List[Car], strategy: DispatchStrategy):
        self.cars, self.strategy = cars, strategy

    def assign(self, floor: int, direction: str) -> Optional[Car]:
        return self.strategy.choose(self.cars, floor, direction)


fleet = [Car(1, position=2, pending=6), Car(2, position=9, pending=0)]
d = Dispatcher(fleet, NearestCarStrategy())
assert d.assign(4, "up").id == 1              # car 1 is closer...

d.strategy = LookCostStrategy(stop_penalty=2)
# cost = distance + 2 * already-queued stops
# car 1:   2 + 2 * 6 = 14
# car 2:   5 + 2 * 0 = 5
assert d.assign(4, "up").id == 2              # ...but car 2 is sooner

# ABC is enforced, not documentation: the bare interface cannot be built.
try:
    DispatchStrategy()
    raise AssertionError("an abstract strategy was instantiated")
except TypeError:
    pass

# `can_serve` is the eligibility gate the express-car extension is built on,
# and it is asked BEFORE any car is scored -- so a fleet with no eligible car
# returns None rather than a bad assignment.
express = Car(3, position=20, serves=range(20, 21))
assert express.can_serve(20) and not express.can_serve(4)
assert NearestCarStrategy().choose([express], 4, "up") is None

DispatchStrategy(ABC) inherits from ABC, short for abstract base class: a class Python refuses to instantiate directly, so DispatchStrategy() raises TypeError instead of silently producing a policy that decides nothing. @abstractmethod marks choose as the method every subclass must supply, and the ... in its body is the literal Ellipsis standing in for “no implementation here”.

The Car here is a stand-in because a dispatch policy needs only four facts about a car: where it is, how much work it has, how long the oldest of that work has waited, and whether it may serve this floor. Its serves=range(1, 21) default is the twenty floors, and can_serve is the eligibility predicate the express-car extension builds on. The direction is a plain "up" string because neither strategy here reads it; they decide on position and load alone. A real controller would pass the Direction, or the whole HallCall.

Follow the two assertions that flip. Car 1 sits at floor 2 with six queued stops; car 2 sits at floor 9 with none. NearestCarStrategy compares only distance, so car 1 wins (gap 2 against 5). LookCostStrategy adds two floors of penalty per queued stop, so car 1 costs 2 + 2*6 = 14 against car 2’s 5 + 2*0 = 5, and the answer flips. That pair is the design in two lines: the same call, two policies, two answers, and Dispatcher never changed.

Extensions

Three follow-ups. For each, the useful answer has the same four parts: what changes, what does not, why the design absorbed it, and what it still costs.

Express cars that only serve floors 20 and above

What changes. One field on the car (serves, the floors it may answer) and one filter in the strategy. Both already exist as Car.serves and Car.can_serve, with a worked express car at the end of Part 3: Car(3, position=20, serves=range(20, 21)) is rejected for a floor-4 call and choose returns None. Nothing changes in ElevatorCar.advance_to_next_stop, because LOOK does not care why a floor is not in its set.

What does not change. The request model, the dispatcher and the car state machine.

Why the design absorbed it. Dispatch already asks each car whether it can take a call before scoring it, keeping eligibility and preference as two separate questions. Fold eligibility into the cost function as “return infinity” and every new strategy has to re-implement the express rule.

The catch. A hall call at floor 25 DOWN and one at floor 5 UP are now served by disjoint car sets, so the building has two independent queues and the fairness bound is per-set, not global. If every express car is busy, a floor-25 passenger waits behind express traffic no matter how idle the local cars are.

A service mode that removes a car from dispatch

What changes. One boolean, already present as in_service, plus the door interlock (the safety circuit that refuses to let a car move while its doors are open) so a technician can hold the doors without the car being scheduled.

What does not change. Nothing in scheduling moves. can_serve returns False and the car is invisible to every strategy at once.

Why the design absorbed it. The car’s availability lives on the car and is consulted by the policy, instead of the dispatcher keeping its own list of active cars. That separate list is the design that breaks: two sources of truth that drift the first time a car goes out of service holding pending calls.

The real question. What happens to the calls already queued on that car. Two honest answers: drain them first (in_service=False blocks new assignments only), or reassign them immediately. Draining fits maintenance; immediate reassignment fits a fault.

Optimizing for wait-time fairness instead of total travel

What changes. One new FairnessStrategy, and the requests need to carry an arrival timestamp. The HallCall dataclass does not have one yet, but adding a field to a Command object is a one-line change, which is part of what modelling requests as objects bought.

What does not change. ElevatorCar, Dispatcher and the diagram.

The block below is the new policy plus three assertion groups: the aging term flipping the answer, the same class with the weight set to zero reverting to nearest-car, and a demonstration that the tempting version of aging does nothing at all. That last one is the point.

from typing import Optional, Sequence


class FairnessStrategy:
    """Score by the worst wait the assignment creates, not the mean.

    Minimizing total travel is a utilitarian objective: it will happily make
    one passenger wait 4 minutes to save six passengers 20 seconds each.

    Aging cannot live in the per-car score as a function of THIS call: `age`
    is the same number for every candidate car, and subtracting a constant
    from every score cannot change the argmin. It has to weight the CALL
    against other calls, or weight each car by the age of the work it is
    already carrying. This class does the second.
    """

    def __init__(self, now: float, aging_weight: float = 3.0):
        self.now, self.aging_weight = now, aging_weight

    def _staleness(self, car) -> float:
        since = car.oldest_waiting_since()
        return 0.0 if since is None else self.now - since

    def choose(self, cars, floor: int, direction: str, waiting_since: float):
        ok = [c for c in cars if c.can_serve(floor)]
        if not ok:
            return None
        # Penalise a car by how long ITS oldest pending call has waited, so a
        # car already carrying a stale request stops accumulating new ones.
        return min(ok, key=lambda c: abs(c.position - floor)
                   + self.aging_weight * self._staleness(c))


now = 10.0
fleet2 = [Car(1, position=2, pending=6, oldest_since=0.0),   # holding a 10s-old call
          Car(2, position=9, pending=0)]                     # idle, nothing stale

assert NearestCarStrategy().choose(fleet2, 4, "up").id == 1          # closest wins
assert FairnessStrategy(now).choose(fleet2, 4, "up", waiting_since=now).id == 2
# car 1:  2 + 3.0 * 10 = 32        car 2:  5 + 3.0 * 0 = 5

# ...and the aging term is what flipped it: at weight 0 it is nearest-car again.
assert FairnessStrategy(now, aging_weight=0.0).choose(
    fleet2, 4, "up", waiting_since=now).id == 1

# Why the tempting version does nothing. `age` is one number for the whole
# call, so subtracting it moves every candidate's score by the same amount.
age = now - 0.0
plain = [abs(c.position - 4) for c in fleet2]
aged = [s - 1_000_000.0 * age for s in plain]
assert min(range(2), key=plain.__getitem__) == min(range(2), key=aged.__getitem__)

Utilitarian here means an objective that maximizes the total across everyone and is indifferent to how it is distributed, which is what lets a policy sacrifice one passenger for six.

The working version ages by penalizing a car in proportion to how long its own oldest pending call has waited, so a car already carrying a stale request stops accumulating new ones. That flips the answer to car 2 in the first assertion, and setting the weight to zero flips it back to car 1.

The tempting version does nothing. The natural instinct is to subtract aging_weight * age from every car’s score, where age is this call’s age. But age is one number for the whole call, the same constant on every candidate, and subtracting a constant from every score cannot change which car wins. The last assertion runs that non-fix: a weight of a million against ten seconds shifts both scores and leaves the argmin exactly where it was. An aging term that only ever moves every score by the same amount does nothing at all; it is documentation, not a working policy. Aging can bite when you choose which call to serve next; it cannot bite when you choose which car serves one given call.

One wrinkle: choose here takes an extra waiting_since argument, so this class does not satisfy the DispatchStrategy signature, and does not subclass it in the code either. The two clean repairs are to put the arrival timestamp on the call object and pass the call instead of a bare floor, or to widen the interface for every strategy. Adding a parameter for one implementation is the classic way an interface starts to rot.

This is the honest version because the objective genuinely conflicts. Total travel and p99 wait cannot both be minimized; the aging term deliberately makes the fleet travel further so the oldest call gets picked up. The design does not pretend one policy is strictly better; it states the trade.

Design questions and edge cases

Seven follow-ups this problem reliably produces, and the answer to each.

Question	Answer
Why not just FCFS?	58 floors versus 24 on the burst above, and the gap grows with load: FCFS costs a flat 6.65 floors/request while LOOK costs 38/m
Does the scheduler starve anyone?	Not LOOK: served within one sweep, so worst case is 38 floors. Nearest-first does starve, per the lobby-traffic sequence above
Where does the direction on a hall call matter?	The stop filter on the sweep. Without it a down-bound car stops for up-bound passengers who then ride the wrong way
Make the dispatcher a Singleton?	No. A Singleton is a class rigged so only one instance can ever exist. One dispatcher per building is a deployment fact, not a language constraint. Construct it once and inject it. A Singleton makes a two-building test impossible and hides the dependency from every call site
Where is the concurrency?	Two hall calls for the same floor+direction must collapse to one, and assignment must be atomic (indivisible, so no thread sees a half-done assignment) or two cars answer the same call. Put the pending-call set behind one lock in the dispatcher; the car’s own queue is touched only by its control loop and needs no lock. None of this is in the single-threaded code here; it is the next thing to build
What if a car’s position sensor lies?	Position is an observation, not owned state. Reconcile against floor sensors and enter a fault mode on disagreement, which sets `in_service = False`, reusing the service-mode path
Capacity?	A car at capacity should stop for `CarCall`s but skip `HallCall`s. That is one predicate in the sweep filter, not a new class

Conclusion

The object model is the easy half; the scheduler is the design. A few load-bearing points:

Two request types. HallCall(floor, direction) and CarCall(floor), because the direction is exactly what the sweep filter needs and a car call has no direction to carry.
LOOK for per-car stop order: finish the current direction, then reverse; never wrap to the bottom (that is SCAN, which wastes a full traverse). On the sample burst it travels 24 floors where FCFS travels 58, and its per-request cost keeps falling with load while FCFS stays flat near 6.65 floors/request.
LOOK bounds worst-case wait at one sweep (38 floors), but only because sweep_target is frozen when the sweep begins. Recompute it every step and the far end starves exactly as nearest-first (SSTF) does.
Strategy for fleet dispatch, because dispatch policy is what changes; per-car sweep order is hard-coded because it does not. That asymmetry is a deliberate bet. Eligibility (can_serve) is a separate question from preference.
Command (requests as objects) buys an audit log and deterministic replay, at the cost of an allocation per press.
Do not model Floor as a class, make Dispatcher a Singleton, or make door timing a Strategy.

The transferable habit is naming what a class structure assumes: which fields are bets on what varies, and which combinations of state and event the code silently leaves undefined.