Minimum workers with first-free job assignment

Clarify first. Are intervals half-open (a job ending at 10 frees its worker for a job starting at 10: yes)? How are jobs with the same start ordered (by job id)? Are worker ids reused (yes: "lowest-numbered free worker", so ids stay small and the answer is deterministic)? In Part 2, does a waiting job hold up the jobs behind it (yes: the queue is first in, first out)?

Part 1: as many workers as needed. This is the classic "minimum meeting rooms" problem with one extra rule: which worker gets each job. Two min-heaps do it:

• busy: (end_time, worker_id) for workers running a job.
• free: worker ids that are idle, smallest first.

Process jobs by (start, job_id). Before placing a job, move every worker whose job ended at or before its start from busy to free. Take the smallest id from free, or hire worker len(hired) if none is free. The number of workers ever hired is the minimum possible, because a new worker is only hired when every existing one is busy at that instant: that many jobs overlap there, so no schedule could use fewer.

Why the free heap matters. A common bug is to give the job to whichever worker finished first (the top of busy). That is a valid schedule with the same worker count, but not "lowest-numbered free worker", and the assignment test fails. Moving all finished workers into free first and then taking the minimum id is what makes it deterministic.

Part 2: a fixed pool of k workers. Now a job may have to wait. Keep the jobs in order; each job starts at the later of its release time, the previous job's start time (first in, first out), and the moment some worker is free. If nobody is free at that moment, advance the clock to the earliest end time in busy, then release every worker that is free by then and take the lowest id. The job keeps its duration.

Worked example. Jobs a [0, 10), b [2, 5), c [5, 12), d [10, 11):

• a → worker 0. b at 2: worker 0 busy → hire worker 1.
• c at 5: worker 1 finished at 5 → worker 1.
• d at 10: worker 0 finished at 10 → worker 0. Two workers in total.
• With k = 1: a runs [0, 10); b waits until 10 and runs [10, 13); c waits until 13, [13, 20); d [20, 21).

import heapq


def assign_workers(jobs):
    """jobs: [(job_id, start, end)] half-open. Lowest-numbered free worker wins.
    Returns (workers needed, {job_id: worker})."""
    busy, free, assignment, hired = [], [], {}, 0
    for job_id, start, end in sorted(jobs, key=lambda j: (j[1], j[0])):
        while busy and busy[0][0] <= start:
            heapq.heappush(free, heapq.heappop(busy)[1])
        if free:
            worker = heapq.heappop(free)
        else:
            worker, hired = hired, hired + 1
        assignment[job_id] = worker
        heapq.heappush(busy, (end, worker))
    return hired, assignment


def schedule_with_pool(jobs, k):
    """k workers, jobs served first in, first out by (release, job_id).
    Returns {job_id: (worker, start, finish)}."""
    if k < 1:
        raise ValueError("need at least one worker")
    busy, free = [], list(range(k))
    heapq.heapify(free)
    result, last_start = {}, None
    for job_id, release, end in sorted(jobs, key=lambda j: (j[1], j[0])):
        duration = end - release
        t = release if last_start is None else max(release, last_start)
        while busy and busy[0][0] <= t:
            heapq.heappush(free, heapq.heappop(busy)[1])
        if not free:
            t = busy[0][0]  # wait for the first worker to finish
            while busy and busy[0][0] <= t:
                heapq.heappush(free, heapq.heappop(busy)[1])
        worker = heapq.heappop(free)
        result[job_id] = (worker, t, t + duration)
        heapq.heappush(busy, (t + duration, worker))
        last_start = t
    return result

• Sorting: O(n log n). Each job pushes and pops each heap at most once: O(n log w) where w is the number of workers.
• Space: O(n) for the result plus O(w) for the heaps.
• A sweep over sorted start and end times finds the count in O(n log n) without heaps, but it cannot say which worker gets which job; the heaps are needed for the assignment.

1. Workers with different speeds or skills. Keep one free heap per skill, or pick the free worker that minimizes finish time; determinism then needs an explicit tie-break rule.
2. Jobs arrive online. The same heaps work as a streaming scheduler: release finished workers on each arrival, and the worker count only grows when everyone is busy.
3. Minimize workers subject to a maximum wait. Binary-search k with schedule_with_pool as the check: O(n log n log n).
4. Priorities. Replace first in, first out with a priority queue of waiting jobs; then starvation needs aging (raise priority with waiting time).
5. Distributed workers. With workers on many machines, lowest-id assignment needs a coordinator; in practice you give up global determinism and use work stealing or a shared queue.

Mid-level (L4)

• Finds the minimum worker count with a sweep or a heap of end times, with half-open intervals right.
• Produces a valid assignment.
• Handles empty input and ties.

Senior (L5)

• Uses a busy heap plus a free heap so the assignment is exactly "lowest-numbered free worker", and explains why taking the first-finished worker is wrong.
• Argues that the count is minimal.
• Extends to a fixed pool with waiting and first-in, first-out order.

Staff (L6+)

• Discusses online arrival, priorities and starvation, and heterogeneous workers.
• Turns "minimum workers for a latency target" into a search over k.
• Explains what determinism costs in a distributed scheduler.