Assign Minimum Workers to Jobs
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a line-delimited text stream representing jobs. Each job record contains a start time and a duration, for example `1030 30`, meaning the job starts at 10:30 and runs for 30 minutes.
Interpret the start time as `HHMM` on the same day, convert it to minutes after midnight, and compute the end time by adding the duration in minutes. Jobs are numbered by input order starting from `0`.
Assign workers to jobs so that no worker handles overlapping jobs.
Your task is to determine:
1. The minimum number of workers required to process all jobs.
2. The assignment history for every job in the format `J<i> W<j>`, meaning job `i` is handled by worker `j`.
Rules:
- Worker IDs start at `0`.
- If multiple workers are free when a job starts, assign the job to the free worker with the smallest worker ID.
- If no worker is free, create a new worker with the next smallest unused ID.
- Return or print the final job-to-worker mapping in job index order.
- If multiple jobs have the same start time, process the smaller job index first.
Design an algorithm and analyze its time complexity.
Quick Answer: This question evaluates a candidate's understanding of interval scheduling, resource allocation, and time arithmetic for converting HHMM timestamps to minute offsets and mapping jobs to non-overlapping worker assignments.
You are given a line-delimited text stream of job records. Each non-empty line contains a start time and a duration, such as `1030 30`, meaning the job starts at 10:30 and lasts 30 minutes. Convert each start time from `HHMM` into minutes after midnight, then compute the end time by adding the duration.
Jobs are numbered by their input order starting from `0` (ignoring blank lines). Assign workers to jobs so that no worker handles overlapping jobs. A worker whose previous job ends exactly when another job starts is considered free.
Your task is to return:
1. The minimum number of workers needed to process all jobs.
2. The assignment history for every job in the format `J<i> W<j>`, where job `i` is assigned to worker `j`.
Assignment rules:
- Worker IDs start at `0`.
- If multiple workers are free when a job starts, assign the free worker with the smallest worker ID.
- If no worker is free, create a new worker with the next smallest unused ID.
- If multiple jobs have the same start time, process the smaller job index first.
- Return the final job-to-worker mapping in original job index order.
Constraints
- 0 <= number of job records <= 100000
- Each start time is a valid same-day time in HHMM format: 0000 to 2359
- 0 <= duration <= 1440
Examples
Input: "1030 30\n1045 20\n1100 15\n1110 30"
Expected Output: (2, ['J0 W0', 'J1 W1', 'J2 W0', 'J3 W1'])
Explanation: Job 0 and Job 1 overlap, so two workers are needed. Job 2 starts when Job 0 ends, so worker 0 can be reused. Job 3 starts after Job 1 ends, so worker 1 can be reused.
Input: "0900 60\n0900 30\n0930 20\n1000 10"
Expected Output: (2, ['J0 W0', 'J1 W1', 'J2 W1', 'J3 W0'])
Explanation: Jobs 0 and 1 start at the same time, so they need different workers. Because ties are processed by smaller job index first, Job 0 gets worker 0 and Job 1 gets worker 1. Later jobs reuse the smallest available worker ID.
Input: ""
Expected Output: (0, [])
Explanation: No jobs means no workers are needed and there are no assignments.
Input: "0030 10\n0040 0\n0040 5"
Expected Output: (1, ['J0 W0', 'J1 W0', 'J2 W0'])
Explanation: Job 0 ends at minute 40. Job 1 starts at 40 and has zero duration, so the same worker can take it. Job 2 also starts at 40 and can still reuse worker 0 because Job 1 ends immediately.
Hints
- Sort jobs by start time, but keep each job's original index so you can build the final answer in input order.
- Use one min-heap for busy workers by end time and another min-heap for currently free worker IDs.