design an elevator

i know designing an elevator is a common System Design problem, but I was motivated to actually look into this after waiting for lots of elevators during my first japan trip

start basic and naive before optimizing

considering a single elevator for the building

naive approach:
- just FIFO on requests, obviously inefficient
  - IN: floor 1 (wants to go to 9) → floor 3 (wants to go to floor 7)
  - OUT: 1→3→9→7
- sort by closest floor
  - IN: floor 1 (wants to go to 9) → floor 3 (wants to go to floor 7)
  - OUT: 1→3→7→9
  - problems
    - if super naive, obvi inefficient to keep flipping directions (go up, down, up)
thoughts/observations
- it seems like elevators complete everything in one direction before flipping…?
hypothesis
- priority queue checking
  - direction matches current direction
  - sort by an input request’s starting floor, then input request’s destination floor
- edge cases
  - consider input requests as [START→END]
  - what if we have requests [1→9, 3→7] and as the elevator moves, we have a new request [4→6]? we should stop at floor 4 and 6 before 7 and 9
    - OUT: 1→3→4→6→7→9
  - a request going in the opposite direction (such as 3→2) is blocked

what about 2 elevators? more complicated when we have multiple elevators available - which to allocate?

base case: two unused elevators - arbitrary which to allocate
base case: one elevator going up, one unused - allocate unused
both elevators higher and going up, new request → elevator that finishes highest request first will be sent

what is the optimization goal?

jennypng