Data Labeling Task Scheduler

Problem Overview

This OpenAI Machine Learning Engineer question was reported as a multi-part coding problem about constructing a schedule for data labeling work.

• Part 1 is the easy version: build any valid schedule.
• Part 2 adds stronger fairness constraints that must hold at every prefix of the returned list.
• Part 3 is a streaming followup: tasks arrive in daily batches and the scheduler must update incrementally.

Problem Statement

You are given:

• t tasks, indexed 0..t-1
• m models, indexed 0..m-1
• h human labelers, indexed 0..h-1
• a target k

Return a scheduling, represented as a list of tuples:

(task, model, human)

Each tuple means:

• human human works on task task
• that assignment is paired with model model

Your schedule must satisfy:

1. Every human labeler participates in at least k assignments total.
2. Every (task, human) pair appears at most once.
3. For every task x, and for every prefix of the schedule, the counts across models stay balanced:

max_i count_prefix(x, model=i) - min_i count_prefix(x, model=i) <= 1

4. For every task x, and for every prefix of the schedule, the counts across humans also stay balanced:

max_j count_prefix(x, human=j) - min_j count_prefix(x, human=j) <= 1

If no valid schedule exists, return failure in whatever form your language uses (None, empty list, exception, etc.).

Part 1: Build Any Valid Schedule

Ignore the prefix-balance constraints for now. Just return any schedule such that:

• each human appears at least k times
• each human works on a given task at most once

Part 2: Prefix-Balanced Schedule

Now add the stronger requirement that the schedule must remain balanced at every intermediate point, not just at the end.

This sounds more complicated than it is. The clean construction is:

1. Schedule work in exactly k rounds.
2. In each round, every human gets exactly one assignment.
3. Rotate tasks cyclically so each human sees a new task each round.
4. For each task, assign models in local round-robin order.