Bugnik
← All problems

02Last-Mile Slot Scheduler

C++EasyBug fixSuggested time: 60 min

Delivery slot scheduler (key=value manifests)

Sign in to start

Before you start

You'll get more out of this problem if you're comfortable with:

Language

  • Splitting a C++ project into headers (.h) and sources (.cpp), and how declarations must match definitions
  • const member functions, and why the compiler cares about them
  • Integer vs floating-point arithmetic and static_cast in C++

Libraries and frameworks

  • std::vector, std::map, std::sort vs std::stable_sort, and std::optional

Build and test tools

  • Reading g++ error messages and test-failure output to find the first real problem
  • Running the tests and filtering them by name

Reasoning

  • Inclusive vs exclusive boundaries when comparing time intervals

Background

The Last-Mile Delivery team at a large online retailer plans which van delivers each customer order and when. Every evening dispatchers load tomorrow's van slots and customer orders, run the scheduler, and print a summary to check how full each van is. After the latest release, dispatchers say orders are going unscheduled and the summary numbers look wrong.

How the system works

Times

  • Times are 24-hour clock strings H:MM or HH:MM (7:45, 09:05, 17:30). Hours are 0–23 and minutes are exactly two digits 00–59. Anything else is a ParseError.
  • Internally a time is minutes after midnight (09:05 → 545). formatClock always prints two-digit hours (09:05).
  • A window is HH:MM-HH:MM (spaces around - allowed). The start must be strictly before the end.

Input files

Both files use one record per line, as key=value pairs separated by ;. Keys are case-insensitive, values are trimmed, unknown keys are ignored, and blank lines or lines starting with # are skipped.

slot=S1; zone=North; start=09:00; end=11:00; capacity=12
order=O1; zone=north; packages=3; window=09:00-12:30
  • Slots require slot, zone, start, end, capacity. capacity is a positive integer, and start must be before end.
  • Orders require order, zone, packages, window. packages is a positive integer.
  • Duplicate slot ids or duplicate order ids are a ParseError, as is any missing or invalid field.

Scheduling rules

  1. Slots are tried earliest start first. Slots with the same start are tried in slot-id order (string comparison).
  2. Orders are processed tightest deadline first (smallest window end). Orders with the same deadline keep their input order.
  3. An order fits a slot when all of these hold:
    • the zone matches (case-insensitive, surrounding whitespace ignored)
    • the whole slot lies inside the order's window: window start <= slot start and slot end <= window end. A slot that starts exactly at the window start or ends exactly at the window end is allowed.
    • the slot's remaining capacity (capacity − used) is at least the order's packages. A slot may be filled to exactly its capacity.
  4. Each order goes to the first slot it fits, and that slot's used grows by the order's packages.
  5. An order that fits no slot is unassigned, with one reason:
    • NO_ZONE: no slot is in the order's zone
    • NO_WINDOW: slots exist in the zone, but none lies inside the window
    • NO_CAPACITY: at least one slot is in the zone and inside the window, but none has room

Route summary

  • Per slot: number of orders assigned, packages assigned, capacity, and utilization = used / capacity × 100 as a real number (7 of 12 → 58.333…). A slot with capacity 0 has utilization 0.
  • Totals: total packages, total capacity, overall utilization (total packages / total capacity × 100, or 0 when there is no capacity), and the number of unassigned orders.
  • formatSummary prints one line per slot (in schedule order) and a final TOTAL line. Percentages have one decimal place:
A1 Harbor 08:00-10:00 orders=2 packages=7/12 util=58.3%
A2 Harbor 10:00-12:00 orders=1 packages=1/8 util=12.5%
TOTAL packages=8/20 util=40.0% unassigned=1

Project structure

include/
  util.h            ParseError, trim / toLower / split, positive-int parsing
  time_util.h       clock parsing and formatting, delivery windows
  slot.h            Slot, Order, Reason
  parser.h          slot and order manifest parsers
  scheduler.h       schedule(): assigns orders to slots
  route_summary.h   per-slot and total utilization, text report
src/                implementations of the above
tests/              unit tests (testlib.h is the test framework, runner.cpp the entry point)

Your task

Dispatchers have reported problems since the last release:

  • The project no longer builds.
  • Customers who are home until exactly the end of a van's slot never get that slot.
  • The route summary shows almost every van at 0% utilization, even when vans are clearly loaded.

Find and fix the defects so that all tests pass.

  • Do not modify files in tests/.
  • Keep your changes minimal. Fix the defects; don't rewrite modules.
  • Additional hidden tests check the behaviour described in this README.