Elevator System

The elevator problem tests scheduling and state. An elevator shouldn't zig-zag between requests in arrival order; it should keep going in one direction, serving every stop on the way, then reverse. That's the SCAN (or "elevator") algorithm, and two heaps make it straightforward.

Requirements#

Start with a single elevator and clear rules for which request it serves next:

1. A building has N floors and one elevator.
2. Each floor has UP and DOWN call buttons outside the elevator.
3. Inside, there are N buttons, one per floor.
4. When idle, the elevator waits at its current floor and serves the next request.
5. While moving, it serves requests in its current direction first. Requests in the other direction wait until the current sweep is done.

Actor: passengers.

Clarifications: one elevator; no access restrictions on floors.

Out of scope: UI, concurrency, door timing, weight limits.

Core entities#

Two enums and one class are enough:

Relationships#

With a single elevator, Elevator is both the entity and the orchestrator. In a multi-elevator version, an ElevatorController would own several Elevators and a dispatch strategy.

Key flows#

Two methods drive everything: request adds a stop, and move serves the next one.

Request(floor, direction):

1. Validate the floor.
2. If it's the current floor, open the doors.
3. Otherwise, push it onto pending_up (min-heap, served ascending) or pending_down (max-heap via negated values, served descending).
4. Wake up if idle.

Move (one tick):

1. Pick the next target in the current direction.
2. If that heap is empty but the other isn't, reverse.
3. If both are empty, go idle.
4. Otherwise, travel to the target, pop it and open the doors.

Why heaps? The next stop going up is always the smallest pending up floor; going down it's the largest pending down floor. Each push and pop is $O(\log n)$.

Code#

The whole design fits in one class:

import heapq
from enum import Enum
from typing import List, Optional


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


class State(Enum):
    IDLE = "IDLE"
    MOVING = "MOVING"
    MAINTENANCE = "MAINTENANCE"


class Elevator:
    def __init__(self, floors: int):
        self.floors = floors
        self.current_floor = 1
        self.direction = Direction.UP
        self.state = State.IDLE
        self.pending_up: List[int] = []    # min-heap of floors
        self.pending_down: List[int] = []  # max-heap via negated floors

    def request(self, floor: int, direction: Direction) -> bool:
        if not (1 <= floor <= self.floors):
            return False
        if floor == self.current_floor:
            self._open_door(floor)
            return True

        if direction == Direction.UP:
            heapq.heappush(self.pending_up, floor)
        else:
            heapq.heappush(self.pending_down, -floor)

        if self.state == State.IDLE:
            self.state = State.MOVING
        return True

    def _next_target(self) -> Optional[int]:
        """Peek the next floor in this sweep.

        Reverses direction if this direction is drained.
        """
        if self.direction == Direction.UP:
            if self.pending_up:
                return self.pending_up[0]
            if self.pending_down:
                self.direction = Direction.DOWN
                return -self.pending_down[0]
        else:
            if self.pending_down:
                return -self.pending_down[0]
            if self.pending_up:
                self.direction = Direction.UP
                return self.pending_up[0]
        return None

    def move(self) -> None:
        """One tick: travel to the next requested floor, open doors."""
        if self.state == State.MAINTENANCE:
            return

        target = self._next_target()
        if target is None:
            self.state = State.IDLE
            return

        self.state = State.MOVING
        if self.direction == Direction.UP:
            heapq.heappop(self.pending_up)
        else:
            heapq.heappop(self.pending_down)

        self.current_floor = target
        self._open_door(target)

        if not self.pending_up and not self.pending_down:
            self.state = State.IDLE

    def _open_door(self, floor: int) -> None:
        print(f"Doors open at floor {floor}")


if __name__ == "__main__":
    e = Elevator(floors=10)
    e.request(3, Direction.UP)
    e.request(5, Direction.UP)
    e.request(2, Direction.DOWN)

    # At floor 1 heading UP: serve 3, then 5, then reverse to serve 2.
    for _ in range(4):
        e.move()
        print("  at:", e.current_floor,
              "| dir:", e.direction.name,
              "| state:", e.state.name)

move() is one tick, so you can call request() between ticks to simulate calls arriving while the elevator is moving.

Extensions and trade-offs#

Interviewers usually push on these points next:

• Requests behind you: an UP request for a floor below the current one (while going up) lands in pending_up and becomes the next target, sending the car backward. A stricter SCAN keeps a third "next sweep" set for such requests and merges it in after reversing.
• Floor-by-floor movement: this model jumps straight to the target. A real simulation moves one floor per tick and checks for stops at every floor.
• Inside vs outside buttons: inside buttons have no direction; infer it from whether the floor is above or below the car.
• Multiple elevators: add an ElevatorController with a DispatchStrategy (nearest idle car, nearest car moving toward the caller, least loaded).
• Maintenance mode: already blocks move(); a controller would stop dispatching to that car.
• Concurrency: buttons are pressed from many threads; guard the heaps with a lock or feed requests through a queue to a single control loop.

Key takeaways#

• SCAN: finish the current direction before reversing.
• Min-heap for up requests, max-heap (negated) for down requests.
• Reverse when the current direction's heap drains; go idle when both are empty.
• Model movement as ticks so new requests can arrive mid-sweep.
• Multi-elevator dispatch is the standard follow-up; make it a strategy.