Assign Tasks to the Minimum Number of Workers
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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++.
```hint Separate busy and reusable workers
The next worker to finish and the smallest worker ID that is already free are different orderings.
```
```hint Release every eligible worker first
Before assigning a task, make all workers whose end time is no later than its start time available for the tie-break.
```
### Examples
```text
tasks = [[60, 30], [70, 10], [90, 15], [60, 5]]
workerIds = [0, 1, 0, 1]
```
```text
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.
Quick Answer: Assign interval tasks to the minimum number of workers while preserving deterministic worker IDs and original output order. Reason about overlapping times, tie handling, resource reuse, efficient scheduling at scale, and boundary cases where one task ends as another begins.
Implement `assignMinimumWorkers(tasks)`.
Each entry of `tasks` is a two-element array `[startMinute, durationMinutes]`. `startMinute` is the minute the task must begin, measured as elapsed minutes from the beginning of one day, and `durationMinutes` is how long the task occupies a worker. A worker handles one task at a time and becomes available again at `startMinute + durationMinutes`.
Assign every task using the **minimum possible number of workers**, and report which worker handled each task.
### Assignment rules
- Tasks are considered in increasing `startMinute`. Tasks that share a start minute are considered in increasing **original input index**.
- Before a task starting at minute `t` is assigned, every worker whose previous task ends at a minute **less than or equal to** `t` is available again. A worker that finishes exactly at minute `t` may begin a task that starts at minute `t`.
- If at least one worker is available, the task goes to the available worker with the **smallest ID**.
- If no worker is available, a new worker is hired. Worker IDs start at `0`, and each newly hired worker receives the next consecutive ID.
### Output semantics
- Return an array of exactly `tasks.length` integers. The order is graded exactly.
- Element `i` is the worker ID assigned to `tasks[i]`, so the result is indexed by **original input position**, not by the order in which the tasks were considered.
- When `tasks` is empty, the answer is exactly `[]`.
- `tasks` must not be modified.
These rules make the answer unique: every input has exactly one correct output array.
### Examples
Example 1:
```text
tasks = [[60, 30], [70, 10], [90, 15], [60, 5]]
returns [0, 1, 0, 1]
```
The two minute-60 tasks are considered first, in input order: `tasks[0]` hires worker `0` (busy until 90) and `tasks[3]` hires worker `1` (busy until 65). At minute 70 only worker `1` is available, so `tasks[1]` reuses it and holds it until 80. At minute 90 both workers are available - worker `0` finishes exactly at 90, which counts as available - so the smallest ID wins and `tasks[2]` goes to worker `0`.
Example 2:
```text
tasks = [[0, 10], [10, 5], [10, 7]]
returns [0, 0, 1]
```
Worker `0` runs `tasks[0]` until minute 10. `tasks[1]` starts exactly at minute 10, so worker `0` is available and is reused instead of a second worker being hired. `tasks[2]` also starts at minute 10, but worker `0` is now busy until 15, so worker `1` is hired.
Example 3:
```text
tasks = [[200, 10], [0, 100], [100, 50], [0, 30]]
returns [0, 0, 0, 1]
```
The input is not sorted by start time. The processing order is `tasks[1]`, `tasks[3]`, `tasks[2]`, `tasks[0]`, which hires worker `0`, then worker `1`, then reuses worker `0` twice. The returned array is still indexed by input position, so it reads `[0, 0, 0, 1]` rather than the processing-order sequence `[0, 1, 0, 0]`.
Constraints
- 0 <= tasks.length <= 12,000
- tasks[i].length == 2, where tasks[i] == [startMinute, durationMinutes]
- 0 <= startMinute < 1,440
- 1 <= durationMinutes <= 1,000,000
- Duplicate tasks and repeated start minutes are allowed
- A task may finish after midnight; all times are elapsed minutes on one common timeline and never wrap back to zero
- Every start, duration, end minute (at most 1,001,439) and worker ID fits in a signed 32-bit integer, so int in Java and int in C++ are wide enough
- Let B be the compact UTF-8 JSON byte length of tasks, counting every bracket, comma and digit: B <= 96,000
- Let R be the compact UTF-8 JSON byte length of the returned integer array: R <= 72,000, so the serialized input plus result is at most 168,000 bytes
- tasks must not be modified
- Target O(n log n) time and O(n) auxiliary space for n = tasks.length
Examples
Input: ([],)
Expected Output: []
Input: ([[0, 10]],)
Expected Output: [0]
Hints
- The minimum worker count is forced, not searched for: a task can only reuse a worker that has already finished, so sweep the tasks in start-time order and never hire while reuse is still possible.
- Two different orderings are live at once. "Which busy worker finishes soonest" and "which idle worker has the smallest ID" are different questions, and one container cannot answer both in logarithmic time.
- Release before you choose, and remember where the answer goes. Every worker whose end minute is less than or equal to the current start must already be idle when the smallest-ID tie-break runs, and each assignment is recorded at the task's original input index.