Least-loaded task assignment with worker specialties

Tasks arrive in a fixed order and must be handed out to a team of workers so that the work stays balanced.

Each task has a unique integer id, a positive integer duration, and (in Part 2) an optional required specialty. Each worker has a unique name and (in Part 2) a set of specialties.

Process the tasks one at a time, in the given order. A worker's load is the sum of the durations already assigned to it; every worker starts at 0. Give each task to the eligible worker with the lowest load. If several eligible workers share the lowest load, pick the one whose name is lexicographically smallest (plain string comparison).

@dataclass(frozen=True)
class Task:
    id: int
    duration: int
    specialty: str | None = None

def distribute(
    workers: dict[str, set[str]], tasks: list[Task]
) -> tuple[dict[str, list[int]], list[int]]: ...

Return a map from each worker name to the ids of its tasks, in assignment order (workers with no tasks map to []), and the list of task ids that could not be assigned.

Part 1. No task has a specialty, so every worker is eligible for every task.

Part 2. A task with a specialty may only go to workers whose set contains it. A task with specialty = None may go to anyone. If no worker has the required specialty, the task is not assigned, no load changes, and its id goes in the unassigned list.

Constraints

• 1 <= len(workers) <= 10^5, 0 <= len(tasks) <= 10^5
• 1 <= duration <= 10^6
• Each worker has at most 10 specialties.

Example 1 (Part 1)

workers = {"bo": {}, "al": {}, "cy": {}}
tasks   = [(10, 4), (11, 2), (12, 3), (13, 1)]   # (id, duration)

10 -> al   loads al=4 bo=0 cy=0   (all tied at 0; "al" is smallest)
11 -> bo   loads al=4 bo=2 cy=0
12 -> cy   loads al=4 bo=2 cy=3
13 -> bo   loads al=4 bo=3 cy=3

result: {"al": [10], "bo": [11, 13], "cy": [12]}, unassigned []

Example 2 (Part 2)

workers = {"alice": {"billing"}, "bob": {"billing", "fraud"}, "cara": {}}
tasks   = [(1, 5, None), (2, 3, "fraud"), (3, 4, "billing"),
           (4, 2, None), (5, 1, "risk"), (6, 6, None)]

1 -> alice  (everyone at 0)
2 -> bob    (only bob has fraud)
3 -> bob    (billing: alice=5, bob=3)
4 -> cara   (alice=5, bob=7, cara=0)
5 -> none   (nobody has risk)
6 -> cara   (alice=5, bob=7, cara=2)

result: {"alice": [1], "bob": [2, 3], "cara": [4, 6]}, unassigned [5]

Aim for better than scanning every worker for every task.

Reconstructed from the reported question; details may differ from what interviewers ask.