Lesson 8 of 12 Case Studies

Design an Elevator System (LLD Case Study)

Elevator system low-level design: hall and car calls, the LOOK scheduling algorithm, a cost-based dispatcher for many cars, and runnable Python code.

45-55 min intermediate 0/12 lessons done
Course contents Lesson 8 of 12 · 0 done
On this page (10 sections)
  1. What you will learn
  2. Requirements
  3. Classes
  4. The LOOK algorithm
  5. Dispatching
  6. The code
  7. Design notes
  8. Key takeaways
  9. Exercises
  10. Quiz

What you will learn

  • How to separate one elevator’s movement from choosing which elevator answers a call.
  • The LOOK (elevator) algorithm for ordering stops.
  • A cost function for dispatching hall calls across several cars.
  • A simple tick-based simulation you can test.

Requirements

  • A building with N floors and M elevators.
  • Hall calls: someone on floor F presses UP or DOWN.
  • Car calls: a passenger inside elevator E presses floor F.
  • Each elevator serves stops efficiently without starving anyone.
  • Assign each hall call to the best elevator.

Usually out of scope: weight limits, door timing, maintenance mode, fire mode. These are good “how would you extend it” answers (maintenance and fire mode fit the State pattern).

Classes

Dispatcher "1" --> "many" Elevator
Elevator: id, floor, direction (UP/DOWN/IDLE), stops: set[int]
Elevator: add_stop(floor), step(), cost(floor, direction)
Dispatcher: hall_call(floor, dir), car_call(id, floor), tick()

The key split: Elevator knows how to move through its own stops; Dispatcher decides which elevator gets a new hall call. Dispatch policy is a natural strategy to swap later.

The LOOK algorithm

Serving stops in arrival order makes the car zig-zag. The classic approach, borrowed from disk scheduling, is SCAN: keep moving in one direction, stopping at requested floors, and reverse only at the end. LOOK is the practical version: reverse as soon as there are no more stops ahead, instead of travelling to the top or bottom floor.

Properties:

  • No starvation: every stop is reached within at most two sweeps.
  • Few direction changes, which is what passengers feel as efficiency.

Dispatching

When a hall call arrives, compute a cost for each elevator and pick the cheapest:

  • Idle: cost = distance.
  • Moving towards the floor in the requested direction: cost = distance (it’s on the way).
  • Otherwise: distance plus a penalty for its pending stops, because it must finish its run first.

Real systems tune this with travel and door times, load and energy, but the structure stays the same.

The code

"""Elevator system low-level design: requests, dispatching and the SCAN (LOOK) algorithm."""
from dataclasses import dataclass, field
from enum import Enum


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


@dataclass
class Elevator:
    id: int
    floor: int = 0
    direction: Direction = Direction.IDLE
    stops: set = field(default_factory=set)

    def add_stop(self, floor: int):
        if floor != self.floor:
            self.stops.add(floor)
        if self.direction is Direction.IDLE and self.stops:
            self.direction = Direction.UP if floor > self.floor else Direction.DOWN

    def step(self) -> int | None:
        """Move one floor (LOOK: keep going while stops remain ahead, then reverse)."""
        if not self.stops:
            self.direction = Direction.IDLE
            return None
        ahead = [s for s in self.stops if (s - self.floor) * self.direction.value > 0]
        if not ahead:  # nothing further this way: turn around
            self.direction = Direction.DOWN if self.direction is Direction.UP else Direction.UP
        self.floor += self.direction.value
        if self.floor in self.stops:
            self.stops.remove(self.floor)
            return self.floor  # doors open here
        return None

    def cost(self, floor: int, direction: Direction) -> int:
        """Rough distance-based cost to serve a hall call; lower is better."""
        distance = abs(self.floor - floor)
        if self.direction is Direction.IDLE:
            return distance
        heading_towards = (floor - self.floor) * self.direction.value >= 0
        if heading_towards and direction is self.direction:
            return distance  # on the way
        return distance + 2 * len(self.stops) + 10  # would need to finish its run first


class Dispatcher:
    def __init__(self, elevators: list[Elevator]):
        self.elevators = elevators

    def hall_call(self, floor: int, direction: Direction) -> Elevator:
        best = min(self.elevators, key=lambda e: (e.cost(floor, direction), e.id))
        best.add_stop(floor)
        return best

    def car_call(self, elevator_id: int, floor: int):
        self.elevators[elevator_id].add_stop(floor)

    def tick(self) -> list[str]:
        events = []
        for e in self.elevators:
            opened = e.step()
            if opened is not None:
                events.append(f"E{e.id} opens at {opened}")
        return events


if __name__ == "__main__":
    d = Dispatcher([Elevator(0, floor=0), Elevator(1, floor=8)])
    print("call at 2 UP ->", f"E{d.hall_call(2, Direction.UP).id}")
    print("call at 9 DOWN ->", f"E{d.hall_call(9, Direction.DOWN).id}")
    d.car_call(0, 6)
    for t in range(1, 8):
        for ev in d.tick():
            print(f"t={t}: {ev}")
        if t == 2:
            d.car_call(0, 4)  # passenger who boarded at 2 presses 4
    print("positions:", [(f"E{e.id}", e.floor, e.direction.name) for e in d.elevators])

Output:

call at 2 UP -> E0
call at 9 DOWN -> E1
t=1: E1 opens at 9
t=2: E0 opens at 2
t=4: E0 opens at 4
t=6: E0 opens at 6
positions: [('E0', 6, 'IDLE'), ('E1', 9, 'IDLE')]

What happened: E0 on floor 0 is closest to the call at 2, and E1 on floor 8 is closest to 9. E0 also had a car call for 6. After the passenger boarded at 2, they pressed 4; because 4 lies ahead in E0’s direction, LOOK stops there before 6 instead of going to 6 first.

Design notes

  • Tick-based simulation makes behaviour deterministic and testable. In a real controller each elevator runs its own loop driven by sensors; the logic is the same.
  • Thread safety: hall calls arrive from many buttons at once. Protect each elevator’s stops with a lock, or feed all events through one queue processed by a single controller thread (simpler and common).
  • Direction-aware stops: a production design keeps separate up and down stop sets so a car going up doesn’t stop for someone who wants to go down. Mention it as an improvement.

Key takeaways

  • Separate per-car movement (LOOK) from fleet-level dispatching (cost function).
  • LOOK reverses only when no stops remain ahead: few direction changes, no starvation.
  • A tick-based model makes elevator logic deterministic and easy to test.
  • Use a single event queue or per-car locks for concurrent button presses.

Exercises

  1. Split stops into up-stops and down-stops so hall calls are served only in the requested direction.
  2. Add a MAINTENANCE state that ignores new calls and finishes current stops.
  3. Change the dispatcher to a nearest-car strategy and compare total ticks for a set of 20 random calls.

Quiz

  1. Why not just serve stops in the order they were requested?
  2. How does LOOK differ from SCAN?
  3. Why does the cost function add a penalty when the elevator is moving away?
Show answers
  1. First-come order causes zig-zagging and long travel times; sweeping in one direction is far more efficient.
  2. SCAN goes to the end of the building before reversing; LOOK reverses as soon as no stops remain ahead.
  3. That elevator has to finish its current run before it can come back, so the real wait is longer than the raw distance.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).