Katkat
Back

Assign Minimum Workers to Jobs

LyftSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manage overlapping intervals and greedy resource allocation using minute-based time arithmetic.

Problem Statement

You are tasked with assigning workers to a series of jobs. Each job has a start time, an end time, and a required number of workers. A worker can only handle one job at a time. Once a worker finishes a job, they are immediately available for another. Your goal is to determine the minimum number of workers required to complete all jobs.

Time is provided in HH:MM format (24-hour clock). A job starting at 10:00 and ending at 11:00 occupies workers during the interval [600, 660) minutes from the start of the day.

Function Signature

def min_workers_required(jobs: List[Tuple[str, str, int]]) -> int:

  • jobs: A list of tuples, where each tuple is (start_time, end_time, worker_count).

Constraints

  • start_time and end_time are in "HH:MM" format.
  • Jobs are guaranteed to have start_time < end_time.
  • The number of jobs is between 1 and 1000.

Examples

Example 1: Input: [('09:00', '10:00', 2), ('09:30', '10:30', 1)] Output: 3 Explanation: At 09:30, we need 2 workers for the first job and 1 for the second, totaling 3.

Example 2: Input: [('08:00', '09:00', 1), ('09:00', '10:00', 1)] Output: 1 Explanation: The first worker finishes at 09:00 and is immediately free to take the second job.

Edge Cases

  • Jobs that end exactly when another begins.
  • Jobs that span across the full day.
  • A single job requiring multiple workers.

Hints

Hint 1

Convert all time strings to total minutes from the start of the day (HH * 60 + MM) to simplify interval arithmetic.

Hint 2

Consider using the 'sweep-line' algorithm: create events for both the start and end of each job, marking worker requirements as positive at the start and negative at the end.

Hint 3

Sort the events by time; if two events occur at the same time, process the 'end' event before the 'start' event to account for immediate worker availability.

Follow-up questions

  • How would your approach change if workers require a 15-minute 'cooldown' period between jobs?
  • If each worker had a limited total capacity (e.g., maximum 8 hours per day), how would you modify the algorithm?
  • What is the time complexity of your solution, and can it be optimized using a min-heap?