Taro Logo

Find Minimum Time to Finish All Jobs II

#632 Most AskedMedium
12 views
Topics:
Binary Search

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 * 105
  • 1 <= jobs[i] <= 109

Solution


Clarifying Questions

When 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:

  1. What are the constraints on the number of jobs and the time each worker takes to complete each job? What is the maximum possible value for the time taken?
  2. Can the time taken by a worker to complete a job be zero?
  3. If it's impossible to complete all jobs (e.g., no workers are available), what should the function return?
  4. Are there any constraints on the data types used for the input (e.g., integers, floats)?
  5. If multiple combinations of worker assignments result in the same minimum time, is any one of them acceptable?

Brute Force Solution

Approach

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:

  1. Consider each job one at a time.
  2. For each job, imagine assigning it to the first worker and calculate the time that worker would take.
  3. Then, imagine assigning that same job to the second worker, and calculate that worker's time.
  4. Keep doing this for every worker, and note down the time each worker would take to complete that specific job.
  5. Now, start trying all combinations. Assign the first job to worker A, the second job to worker B, the third to worker C, and so on. Calculate the total time it would take if that happened. Remember to consider each worker can only work on one job at a time, and that they will work concurrently.
  6. Then, try a different combination. Assign the first job to worker A, the second job to worker B, and the third job to worker D. Again, calculate the total time.
  7. Continue trying every single possible way to assign each job to a worker.
  8. For each combination, keep track of the longest time any worker takes. This is because the jobs are all finished only when the last worker finishes their assigned job.
  9. Finally, after trying every possible combination, choose the one that resulted in the smallest longest time.

Code Implementation

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_time

Big(O) Analysis

Time Complexity
O(m^n) – The brute force approach considers every possible assignment of n jobs to m workers. For each of the n jobs, there are m possible workers to assign it to. Therefore, there are m choices for the first job, m choices for the second job, and so on, resulting in m * m * ... * m (n times) possible combinations. This equates to m^n possible assignments that need to be checked. Thus the algorithm's time complexity is O(m^n).
Space Complexity
O(N!) – The brute force approach explores all possible job assignments to workers. Because we are considering all possible permutations of assigning N jobs to N workers (assuming the number of workers is at least the number of jobs), the recursion depth to generate all such combinations is effectively exploring a decision tree whose number of leaf nodes can reach N! In practice, there will be N recursive calls and the call stack can grow up to O(N) in memory. However the real space complexity comes from the number of permutations being generated, and therefore stored or implicitly tracked during the execution. This leads to a space complexity that grows factorially with the number of jobs and workers, and this overwhelms the small O(N) call stack. Therefore, the total auxiliary space complexity is O(N!).

Optimal Solution

Approach

The 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:

  1. Consider all jobs and each worker's time to complete each job.
  2. Focus on the job that has the lowest time for *any* worker to complete it.
  3. Assign this job to the worker that can finish it the fastest. Importantly, assign a second worker to the same job based on who can complete it second fastest.
  4. Once a worker is assigned, remove them from consideration for future jobs, since they've taken their job.
  5. Repeat the above steps until all jobs are completed. The latest finish time among all workers is the minimum time to finish all jobs.

Code Implementation

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)

Big(O) Analysis

Time Complexity
O(n² log n) – The algorithm iterates through all jobs, which corresponds to n iterations. Inside the loop, finding the job with the overall minimum time across all workers requires iterating through all worker-job combinations which can take O(n) where n is the number of jobs. For each chosen job, the fastest and second fastest worker assignment can involve sorting the worker times, resulting in O(n log n) where n here also represents the maximum number of workers. Because this sorting/search happens within the outer loop that iterates up to n times, the total time complexity becomes O(n * n log n) which simplifies to O(n² log n).
Space Complexity
O(N) – The algorithm needs to keep track of which workers are available for assignment. In the worst-case scenario, each worker might need to be considered until a job is found that they can perform, potentially requiring storing information for all workers. The number of workers to keep track of is implicitly related to the size of the jobs input; specifically, the number of jobs, denoted as N, determines the number of required workers. Therefore, the auxiliary space used is proportional to N, where N is the number of jobs, as we need to keep track of which workers are still available.

Edge Cases

Empty jobs array
How to Handle:
Return 0 since there are no jobs to complete.
Jobs array with only one job
How to Handle:
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
How to Handle:
Use long data type to store time values to avoid integer overflow.
Workers with extremely large or small productivity differences
How to Handle:
The algorithm should correctly identify the optimal assignments even with extreme value differences.
Jobs with extremely short or long durations
How to Handle:
The algorithm needs to correctly account for both very quick and very long job durations.
Equal productivity amongst workers
How to Handle:
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
How to Handle:
The algorithm should efficiently handle the scenario where workers are reused across many jobs.
Negative worker productivity
How to Handle:
Assume that worker productivity will always be positive. Throw error if negative productivity is detected.
0/1718 completed