You are given an integer array jobs, where jobs[i] is the time it takes to complete the ith job.
There are two workers available. You can assign jobs in any order to the workers. Each worker works on one job at a time. Return the minimum time to finish all jobs.
Example 1:
Input: jobs = [1,2,4,7,8] Output: 8 Explanation: Assign the jobs with times 1, 2, and 4 to the first worker. Assign the jobs with times 7 and 8 to the second worker. The first worker will finish the jobs in 1 + 2 + 4 = 7 time units. The second worker will finish the jobs in 7 + 8 = 15 time units. The time needed to finish all jobs is the maximum between them, which is 15. It can be proven that the minimum time needed to finish all jobs is 15.
Example 2:
Input: jobs = [15,13,2,14,5] Output: 17 Explanation: Assign the jobs with times 15 and 2 to the first worker. Assign the jobs with times 13, 14, and 5 to the second worker. The first worker will finish the jobs in 15 + 2 = 17 time units. The second worker will finish the jobs in 13 + 14 + 5 = 32 time units. The time needed to finish all jobs is the maximum between them, which is 32. It can be proven that the minimum time needed to finish all jobs is 32.
Constraints:
1 <= jobs.length <= 2 * 1051 <= jobs[i] <= 109When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach aims to explore all possible ways to assign each job to a worker. We essentially try every possible assignment combination to find the one that results in the minimum completion time. This involves exhaustively testing each worker's suitability for each job.
Here's how the algorithm would work step-by-step:
def find_minimum_time_to_finish_all_jobs_brute_force(jobs):
number_of_jobs = len(jobs)
number_of_workers = len(jobs[0])
minimum_completion_time = float('inf')
def calculate_completion_time(job_assignments):
worker_times = [0] * number_of_workers
# Calculate the time each worker spends.
for job_index, worker_index in enumerate(job_assignments):
worker_times[worker_index] += jobs[job_index][worker_index]
return max(worker_times)
def find_all_assignments(job_index, current_assignment):
nonlocal minimum_completion_time
# Base case: all jobs have been assigned.
if job_index == number_of_jobs:
completion_time = calculate_completion_time(current_assignment)
minimum_completion_time = min(minimum_completion_time, completion_time)
return
# Recursive step: try assigning job to each worker.
for worker_index in range(number_of_workers):
find_all_assignments(job_index + 1, current_assignment + [worker_index])
# Start the recursive process to explore all assignments.
find_all_assignments(0, [])
return minimum_completion_timeThe key to efficiently finding the minimum time is realizing each job needs exactly two workers. We should strategically assign jobs to workers with the shortest completion times first to minimize idle time and overall completion time.
Here's how the algorithm would work step-by-step:
def find_minimum_time_to_finish_all_jobs_ii(jobs):
number_of_jobs = len(jobs)
workers_available = set(range(len(jobs[0])))
job_completion_times = [0] * len(jobs[0])
for _ in range(number_of_jobs):
minimum_time = float('inf')
best_job_index = -1
first_worker_index = -1
second_worker_index = -1
for job_index in range(number_of_jobs):
if jobs[job_index] is not None:
job_times = jobs[job_index]
available_workers_for_job = []
for worker_index in workers_available:
available_workers_for_job.append((job_times[worker_index], worker_index))
available_workers_for_job.sort()
# If no available workers for this job, continue.
if len(available_workers_for_job) < 2:
continue
first_worker_time = available_workers_for_job[0][0]
first_worker = available_workers_for_job[0][1]
second_worker_time = available_workers_for_job[1][0]
second_worker = available_workers_for_job[1][1]
# Need total time of two workers for a job.
total_time_for_job = first_worker_time + second_worker_time
if total_time_for_job < minimum_time:
minimum_time = total_time_for_job
best_job_index = job_index
first_worker_index = first_worker
second_worker_index = second_worker
# Remove the assigned workers.
workers_available.remove(first_worker_index)
workers_available.remove(second_worker_index)
# Update the completion times for the workers.
job_completion_times[first_worker_index] += jobs[best_job_index][first_worker_index]
job_completion_times[second_worker_index] += jobs[best_job_index][second_worker_index]
# Remove the completed job from consideration.
jobs[best_job_index] = None
# Determine if any jobs remain
remaining_jobs = False
for job in jobs:
if job is not None:
remaining_jobs = True
break
if not remaining_jobs:
break
# Need to return the maximum completion time.
return max(job_completion_times)| Case | How to Handle |
|---|---|
| Empty jobs array | Return 0 since there are no jobs to complete. |
| Jobs array with only one job | Return the time taken by the fastest worker since only one worker will perform the job. |
| Large number of jobs and workers potentially leading to integer overflow | Use long data type to store time values to avoid integer overflow. |
| Workers with extremely large or small productivity differences | The algorithm should correctly identify the optimal assignments even with extreme value differences. |
| Jobs with extremely short or long durations | The algorithm needs to correctly account for both very quick and very long job durations. |
| Equal productivity amongst workers | Ensure the algorithm avoids bias towards any particular worker when workers are similarly productive. |
| Number of workers is much smaller than the number of jobs | The algorithm should efficiently handle the scenario where workers are reused across many jobs. |
| Negative worker productivity | Assume that worker productivity will always be positive. Throw error if negative productivity is detected. |