Assign Tasks to the Minimum Number of Workers

Assign Tasks to the Minimum Number of Workers

Problem

Implement assignMinimumWorkers(tasks) -> workerIds.

Each task is [startMinute, durationMinutes]. startMinute is the task's start time measured from the beginning of one day, and durationMinutes is its elapsed processing time. A worker can process only one task at a time and becomes available at startMinute + durationMinutes.

Assign every task while using the minimum possible number of workers. When more than one existing worker is available for a task, choose the available worker with the smallest ID. Worker IDs start at 0 and each newly needed worker receives the next consecutive ID.

Process tasks by increasing start time; tasks with the same start time are processed by their original input index. Return the assigned worker ID for every task in original input order.

Portable Contract

• tasks is a JSON array of two-integer arrays [startMinute, durationMinutes].
• 0 <= tasks.length <= 12,000.
• 0 <= startMinute < 1,440 and 1 <= durationMinutes <= 1,000,000.
• A task may finish after midnight; times are elapsed minutes on one common timeline and do not wrap back to zero.
• Duplicate tasks and equal start times are allowed.
• A worker whose previous task ends at minute t is available for a task starting at minute t.
• Do not modify tasks.
• Let B be the compact UTF-8 JSON byte length of tasks, counting every bracket, comma, and digit. Inputs satisfy B <= 96,000.
• Let R be the compact UTF-8 JSON byte length of the returned integer array. Inputs guarantee R <= 72,000, so the serialized input plus result is at most 168,000 bytes.
• Target O(n log n) time and O(n) auxiliary space for n = tasks.length.

All four languages use homogeneous integer containers: list[list[int]] returning list[int] in Python, nested arrays returning an array in JavaScript, List<List<Integer>> returning List<Integer> in Java, and vector<vector<int>> returning vector<int> in C++.

Examples

tasks = [[60, 30], [70, 10], [90, 15], [60, 5]]
workerIds = [0, 1, 0, 1]

tasks = [[0, 10], [10, 5], [10, 7]]
workerIds = [0, 0, 1]

Discussion Requirements

• Explain why processing by start time and reusing every eligible worker minimizes the worker count.
• Identify the ordering keys for busy workers and available workers.
• Explain the original-index tie-break for equal start times and why the final result is reordered by input index.
• Test empty input, touching tasks, equal starts, simultaneous releases, duplicate tasks, and a case where several free workers are available.