Design an Elevator System

Description

An elevator system is a scheduling problem dressed as an object model: cars that move one floor at a time, requests from inside and outside the cars, a rule for which stop comes next, and - with several cars - a dispatcher deciding which car answers each call. It tests whether you can keep the scheduling rule swappable, the safety rules inside the car, and time under the test's control. This skill builds a car that sweeps (LOOK), a dispatcher, and a step-driven simulation.

An elevator looks like a queue of requests, so the first design is one:

class Elevator {
    int floor = 0;
    Queue<Integer> requests = new LinkedList<>();

    void press(int target) { requests.add(target); }

    void run() throws InterruptedException {
        while (true) {
            Integer next = requests.poll();
            if (next == null) { Thread.sleep(100); continue; }
            while (floor != next) { floor += Integer.signum(next - floor); Thread.sleep(1000); }
            System.out.println("Doors open at " + floor);
        }
    }
}

import time
from collections import deque


class Elevator:
    def __init__(self):
        self.floor = 0
        self.requests: deque[int] = deque()

    def press(self, target: int) -> None:
        self.requests.append(target)

    def run(self) -> None:
        while True:
            if not self.requests:
                time.sleep(0.1)
                continue
            target = self.requests.popleft()
            while self.floor != target:
                self.floor += 1 if target > self.floor else -1
                time.sleep(1)
            print(f"Doors open at {self.floor}")

Presses for floors 9, 1, 8 and 2 make it ride 0 → 9 → 1 → 8 → 2: thirty floors, passing every stop twice before serving it. Pressing 7 five times queues five stops at 7. With three cars, the obvious extension - every car answers every call - sends all three to the same floor. And the only way to test any of it is to sleep through it in real time.

We'll go from simple to more technical:

1. The model: cars, requests, a dispatcher and a step-driven clock.
2. A car that keeps its direction and stops on the way.
3. Scheduling algorithms compared: FCFS, nearest-first, SCAN and LOOK.
4. The bugs, and where safety and concurrency belong.

The approach

1. Clarify. How many floors and cars? Hall calls (someone on floor 5 presses UP) and car calls (someone inside presses 9) - both? What should be optimized: waiting time, travel, energy? Capacity, express zones, emergency modes - in scope or follow-ups?
2. Model. A Direction enum (UP, DOWN, IDLE). A Car with its floor, direction and a set of stops. An ElevatorSystem facade that owns the cars and decides which car takes each hall call.
3. API. requestPickup(floor, direction) returns the assigned car; requestDestination(car, floor); step() advances time by one tick; floorOf, directionOf, stopsServed let tests and displays see the state.
4. Core. Each car runs LOOK: keep going in the current direction while there's a stop ahead, then turn around. A dispatcher gives each hall call to the nearest car that's idle or already heading that way. Time is a method call, not a clock.

The pieces in code

class Car {
    int floor = 0;
    Direction direction = Direction.IDLE;
    final TreeSet<Integer> stops = new TreeSet<>();      // sorted, no duplicates

    void step() {                                         // one tick
        if (stops.remove(floor)) served.add(floor);       // a stop takes the whole tick
        else if (direction == Direction.UP) floor++;
        else if (direction == Direction.DOWN) floor--;
        updateDirection();
    }

    void updateDirection() {                              // LOOK
        if (stops.isEmpty()) { direction = Direction.IDLE; return; }
        if (stops.contains(floor)) return;                // about to stop here: keep the heading
        Integer above = stops.higher(floor), below = stops.lower(floor);
        if (direction == Direction.UP && above != null) return;
        if (direction == Direction.DOWN && below != null) return;
        if (above != null && below != null)               // idle: nearest first, a tie goes up
            direction = above - floor <= floor - below ? Direction.UP : Direction.DOWN;
        else direction = above != null ? Direction.UP : Direction.DOWN;
    }
}

class Car:
    def __init__(self):
        self.floor = 0
        self.direction = Direction.IDLE
        self.stops: set[int] = set()              # no duplicates
        self.served: list[int] = []

    def step(self) -> None:                       # one tick
        if self.floor in self.stops:              # a stop takes the whole tick
            self.stops.remove(self.floor)
            self.served.append(self.floor)
        elif self.direction is Direction.UP:
            self.floor += 1
        elif self.direction is Direction.DOWN:
            self.floor -= 1
        self.update_direction()

    def update_direction(self) -> None:           # LOOK
        if not self.stops:
            self.direction = Direction.IDLE
            return
        if self.floor in self.stops:
            return                                # about to stop here: keep the heading
        above = min((s for s in self.stops if s > self.floor), default=None)
        below = max((s for s in self.stops if s < self.floor), default=None)
        if self.direction is Direction.UP and above is not None:
            return
        if self.direction is Direction.DOWN and below is not None:
            return
        if above is not None and below is not None:   # idle: nearest first, a tie goes up
            self.direction = Direction.UP if above - self.floor <= self.floor - below else Direction.DOWN
        else:
            self.direction = Direction.UP if above is not None else Direction.DOWN

• A TreeSet of stops collapses repeated presses and answers "is there a stop above me?" with higher(floor) in O(log n). Python has no sorted set in its standard library: a plain set with min/max scans, as above, is fine for a car's handful of stops, and bisect over a sorted list (or the sortedcontainers package) gives the O(log n) version.
• step() is the clock. Tests and demos call it; production wraps it in a scheduler that calls it every second. Nothing in the logic sleeps.
• Direction is recomputed after every change - a new request or a step - in one method, so there's a single place that decides when to turn.

The dispatcher is a cost rule over the cars:

boolean isOnTheWay(Car car, int floor, Direction wanted) {
    if (car.direction == Direction.IDLE) return true;
    if (car.direction != wanted) return false;
    return wanted == Direction.UP ? floor > car.floor : floor < car.floor;
}
// pick the nearest car that is on the way (lowest id on a tie); if none is, the nearest car overall

def is_on_the_way(car: Car, floor: int, wanted: Direction) -> bool:
    if car.direction is Direction.IDLE:
        return True
    if car.direction is not wanted:
        return False
    return floor > car.floor if wanted is Direction.UP else floor < car.floor
# pick the nearest car that is on the way (lowest id on a tie); if none is, the nearest car overall

A car at floor 2 heading up to 15 is the right answer for someone at 6 going up - it passes 6 anyway - even when an idle car is closer, because the idle car would make an extra trip. Someone at 9 going down should wait for a car that will actually be heading down.

Scheduling algorithms

With LOOK, any request is served within two sweeps of the shaft: the car finishes its current direction and comes back. Operating systems schedule disk-head movements with the same four algorithms.

Where you'll see it

Modern high-rises use destination dispatch: riders enter their floor at a lobby panel and are told which car to take, so the dispatcher groups people by destination instead of guessing. Controllers switch traffic modes by time of day (up-peak in the morning sends idle cars back to the lobby), and a separate safety system - not the scheduling code - interlocks the doors and the drive. The dispatcher is also where the interesting money is: the cost function (wait time, ride time, energy) is what vendors compete on.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A car at floor 0 gets presses for 9, 1, 8 and 2, in that order. How many floors does FCFS travel, and how many does LOOK?

2. Car A is at 2 heading up to 15; car B is idle at 0. Who should take a pickup at floor 6 going up - and one at floor 9 going down?

3. Why is step() a method instead of a loop that sleeps for a second per floor?

Key takeaways

• Model hall calls and car calls, a Car with a sorted set of stops, and one system object that owns the cars.
• Each car runs LOOK: keep going while stops remain ahead, then turn - no zigzags, no starvation.
• A dispatcher gives each hall call to one car: the nearest that's idle or already heading that way, with a deterministic tie-break.
• Drive time through step() so the simulation is deterministic and testable.
• Safety rules like "never move with the doors open" live inside the car's state, and button presses from many threads go through one queue.