SRTF-Processing — The Straw Hat Treasury

A preemptive Shortest-Remaining-Time-First (SRTF) style scheduler for distributing incoming jobs across multiple workers, built on a hand-rolled generic binary heap. Originally a data-structures assignment, themed around the One Piece Straw Hat crew hauling treasure.

The problem

The Straw Hats have m crewmates (think: workers / processors). Treasures (jobs) arrive over time, each with:

• an id (unique),
• a size (how much processing it needs), and
• an arrival time.

Two things happen:

1. Load balancing. When a treasure arrives, it's handed to the crewmate with the smallest current load (the total remaining work already queued on them). Ties and updates are handled with a min-heap keyed on load.
2. Preemptive scheduling per crewmate. Each crewmate processes its own pile using a priority rule, and can switch to a higher-priority treasure the moment one arrives — i.e. work is preemptible, in the spirit of SRTF. A treasure's priority is derived from its arrival time and its remaining size, so smaller/older jobs finish first (ties broken by id).

The goal is to compute the completion time of every treasure.

Design

Everything is built on one reusable data structure — a binary heap that takes an arbitrary comparison function — so the same Heap class powers both the "least-loaded crewmate" queue and each crewmate's per-job priority queue.

File	Role
heap.py	Generic binary Heap (build / insert / extract / top) parameterized by a comparator. Also defines comparator_load (min-heap on crewmate load) and comparator_priority (min-heap on treasure priority, id as tie-break).
treasure.py	Treasure — holds id, size, arrival time, completion time; computes its scheduling priority() and (re)initializes rem_size.
crewmate.py	CrewMate — owns a priority heap of treasures and tracks its current load.
straw_hat.py	StrawHatTreasury — the orchestrator: assigns treasures to crewmates and simulates processing to produce completion times.
custom.py	Scratch space for any extra helpers.

How the simulation works

StrawHatTreasury.get_completion_time() walks the treasures in arrival order and, between consecutive arrivals, advances a virtual clock:

1. Assign the newly arrived treasure to the least-loaded crewmate (extract the min from the crewmate load-heap, add, then re-insert).
2. Run each active crewmate forward over the gap until the next arrival, draining work from the top of its priority heap. If a treasure finishes inside the window, record its completion_time and pop it; otherwise decrement its remaining size.
3. After the last arrival, process everything to completion.

Returns the list of treasures sorted by id, each with completion_time filled in.

Complexity

With m crewmates and n treasures:

• add_treasure — O(log m + log n)
• get_completion_time — O(n · (log m + log n))

Usage

import treasure
from straw_hat import StrawHatTreasury

# 3 crewmates
t = StrawHatTreasury(3)

# Treasure(id, size, arrival_time) — add in arrival-time order
t.add_treasure(treasure.Treasure(1, 5, 1))
t.add_treasure(treasure.Treasure(2, 4, 4))
t.add_treasure(treasure.Treasure(3, 6, 4))

for job in t.get_completion_time():
    print(f"treasure {job.id}: arrives {job.arrival_time}, "
          f"size {job.size}, completes at {job.completion_time}")

Running

Pure Python, no dependencies:

python straw_hat.py

(A few worked examples are included as comments at the bottom of straw_hat.py — uncomment to run them.)

Notes

• Treasures are expected to be added in non-decreasing arrival-time order.
• rem_size is reset between full runs, so get_completion_time() can be called repeatedly on the same treasury.