Generate Data Labeling Schedules

A data labeling platform manages tasks, AI models, and human annotators. Each entity has a 1-indexed string ID.

You are given four integers: totalTask, totalModel, totalHuman, and k.

• Tasks are labeled "t1", "t2", ..., "t{totalTask}".
• Models are labeled "m1", "m2", ..., "m{totalModel}".
• Human annotators are labeled "h1", "h2", ..., "h{totalHuman}".

An assignment is represented as [task, model, human], meaning the specified human annotates the specified task using the specified model. A task may appear in multiple assignments, so the same task can be annotated by multiple humans and paired with multiple models.

Return any valid schedule as a list of assignments such that:

1. Each human appears in at least k assignments.
2. The same human cannot annotate the same task more than once.
3. Every assignment uses valid task, model, and human IDs within the given ranges.

If no valid schedule exists, return an empty list.

Constraints for the basic version:

• 1 <= totalTask, totalModel, totalHuman <= 100
• 0 <= k <= totalTask

Example 1:

Input:

totalTask = 3, totalModel = 1, totalHuman = 2, k = 2

One valid output:

[["t1", "m1", "h1"], ["t2", "m1", "h2"], ["t2", "m1", "h1"], ["t3", "m1", "h2"]]

Explanation: Each human annotates 2 distinct tasks. Human "h1" works on "t1" and "t2", while "h2" works on "t2" and "t3". No human annotates the same task twice.

Example 2:

Input:

totalTask = 1, totalModel = 1, totalHuman = 1, k = 1

One valid output:

[["t1", "m1", "h1"]]

Example 3:

Input:

totalTask = 2, totalModel = 3, totalHuman = 3, k = 2

One valid output:

[["t1", "m1", "h1"], ["t2", "m1", "h2"], ["t1", "m1", "h3"], ["t2", "m1", "h1"], ["t1", "m1", "h2"], ["t2", "m1", "h3"]]

Follow-up: return a prefix-balanced schedule.

A prefix is the first x assignments in the schedule for any x >= 1. For example, a schedule with 4 assignments has 4 prefixes: the first assignment, the first 2 assignments, the first 3 assignments, and the full schedule. The balance requirements below must hold for every prefix, not only for the final schedule.

A schedule is prefix-balanced if it satisfies both conditions for every prefix:

1. Task-model balance: For each task, the number of times that task is assigned to each model must differ by at most 1, including models with zero uses. Formally, for every task, max_count(task, model) - min_count(task, model) <= 1.
2. Human-model balance: For each human, the number of times that human uses each model must differ by at most 1, including models with zero uses. Formally, for every human, max_count(human, model) - min_count(human, model) <= 1.

Return any valid prefix-balanced schedule. If no such schedule exists, return an empty list.

Constraints for the follow-up:

• 1 <= totalTask, totalModel, totalHuman <= 10
• 0 <= k <= totalTask

Follow-up example 1:

Input:

totalTask = 3, totalModel = 2, totalHuman = 4, k = 2

One valid output:

[["t1", "m1", "h1"], ["t1", "m2", "h2"], ["t1", "m1", "h3"], ["t1", "m2", "h4"], ["t2", "m2", "h1"], ["t2", "m1", "h2"], ["t2", "m2", "h3"], ["t2", "m1", "h4"]]

Follow-up example 2:

Input:

totalTask = 1, totalModel = 1, totalHuman = 1, k = 1

One valid output:

[["t1", "m1", "h1"]]

Follow-up example 3:

Input:

totalTask = 3, totalModel = 1, totalHuman = 3, k = 2

One valid output:

[["t1", "m1", "h1"], ["t1", "m1", "h2"], ["t1", "m1", "h3"], ["t2", "m1", "h1"], ["t2", "m1", "h2"], ["t2", "m1", "h3"]]