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