Jobs

Interviews

Discussions

Find Minimum Time to Finish All Jobs

Hard

Asked by:

More companies

37 views

Topics:

ArraysBinary SearchRecursionDynamic Programming

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Try coding it in LeetCode

Find Minimum Time to Finish All Jobs

Hard

Asked by:

37 views

Topics:

ArraysBinary SearchRecursionDynamic Programming

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th job.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Try coding it in LeetCode

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:

What is the range of values for the time each job takes?
Can any job have a time of 0?
Are there any constraints on the number of workers available?
If it's impossible to complete all jobs within any finite time, what should I return?
Is the input list of jobs guaranteed to be non-empty?

Brute Force Solution

Approach

The brute force method for finding the minimum time to finish all jobs involves exploring every possible way to assign jobs to workers. We systematically try all combinations of job assignments. We then find the best outcome from all the tried scenarios.

Here's how the algorithm would work step-by-step:

Consider each job one by one.
For each job, explore all possible workers that it could be assigned to.
For each worker that a job can be assigned to, calculate how long that worker would take to complete all their assigned jobs, including the new one.
Consider every combination of job-to-worker assignments. This will result in a lot of different ways the work could be divided.
For each possible division of work, find the worker who takes the longest amount of time to complete all of their assigned jobs. This is the total time it would take to complete all the jobs under that particular division.
Compare the total time for all the different divisions of work. Keep track of the shortest total time you find.
After considering every single possible way to divide the jobs among the workers, the shortest total time you kept track of will be the minimum time to finish all jobs.

Code Implementation

def find_minimum_time_to_finish_all_jobs(job_durations, number_of_workers):
    minimum_time = float('inf')

    def calculate_minimum_time_recursive(index, worker_assignments):
        nonlocal minimum_time

        # Base case: all jobs have been assigned
        if index == len(job_durations):
            maximum_worker_time = 0
            for worker_index in range(number_of_workers):
                maximum_worker_time = max(maximum_worker_time, sum(worker_assignments[worker_index]))
            minimum_time = min(minimum_time, maximum_worker_time)
            return

        # Try assigning the current job to each worker
        for worker_index in range(number_of_workers):
            # Create a new assignment configuration
            new_worker_assignments = [worker_assignments[i][:] for i in range(number_of_workers)]
            new_worker_assignments[worker_index].append(job_durations[index])

            # Recursively explore the next job assignment
            calculate_minimum_time_recursive(index + 1, new_worker_assignments)

    # Initialize worker assignments as empty lists for each worker
    initial_worker_assignments = [[] for _ in range(number_of_workers)]

    # Start the recursive process
    calculate_minimum_time_recursive(0, initial_worker_assignments)

    return minimum_time

Big(O) Analysis

Time Complexity

O(m^n) – The brute force approach explores all possible assignments of n jobs to m workers. For each of the n jobs, there are m possible workers it can be assigned to. This leads to m * m * ... * m (n times) possible assignments, which is m^n. Evaluating the maximum workload for each assignment and comparing to find the minimum doesn't change the fundamental exponential nature of exploring all possible assignments. Therefore, the time complexity is O(m^n).

Space Complexity

O(K^N) – The brute force method explores every possible way to assign N jobs to K workers. The recursion depth for exploring these assignments is N (the number of jobs). At each level of recursion, we potentially iterate through all K workers to assign the current job. This creates an implicit call stack whose maximum depth is N. In the worst-case scenario, each function call might require storing the current assignment configuration, contributing to a space complexity of O(K^N), since each job can be assigned to K possible workers. The algorithm essentially generates a tree where each node represents a job assignment decision and branches out to K possibilities, leading to an exponential increase in space usage.

Optimal Solution

Approach

The best way to solve this problem is to cleverly guess possible completion times and then check if those guesses are actually feasible. We use a binary search approach to efficiently narrow down the correct minimum completion time. This is much better than trying all possible worker assignments.

Here's how the algorithm would work step-by-step:

First, recognize that the minimum possible time is at least as long as the single longest job. Also, the maximum possible time is no longer than the sum of all the jobs.
Now, use binary search within this range of possible completion times. Pick a time in the middle of the range as your guess.
For the current guess, determine if it is possible for a given number of workers to complete all jobs within the time. The key is to greedily assign jobs to each worker until they are full, and move on to the next worker if needed.
If it is possible to complete all jobs within the guess, try a smaller guess. If it's not possible, you will need a larger guess.
Repeat this binary search process of guessing and checking, narrowing the search range, until you find the smallest possible time that allows all jobs to be completed. This will be the minimum completion time.

Code Implementation

def find_minimum_time_to_finish_all_jobs(jobs, number_of_workers):
    start_time = max(jobs)
    end_time = sum(jobs)

    while start_time < end_time:
        mid_time = (start_time + end_time) // 2

        # Check if it's possible to complete within mid_time
        if is_possible_to_complete(jobs, number_of_workers, mid_time):
            end_time = mid_time
        else:
            start_time = mid_time + 1

    return start_time

def is_possible_to_complete(jobs, number_of_workers, max_time_per_worker):
    workers_needed = 1
    current_worker_time = 0

    # Iterate through each job and assign to worker greedily
    for job_duration in jobs:
        if job_duration > max_time_per_worker:
            return False

        if current_worker_time + job_duration <= max_time_per_worker:
            current_worker_time += job_duration
        else:
            # Need a new worker if current can't complete the job.
            workers_needed += 1
            current_worker_time = job_duration

    # If the needed workers exceed the number, not possible.
    if workers_needed <= number_of_workers:
        return True
    else:
        return False

# The is_possible_to_complete checks if a completion time is feasible.
# Based on this result, we adjust the search space

# Binary search to find the minimum completion time.
# We want to find the smallest time all the jobs can be completed

Big(O) Analysis

Time Complexity

O(n log s) – The algorithm uses binary search to find the minimum completion time. The search space, denoted as 's', is the difference between the sum of all job times and the longest job time. The binary search performs log s iterations. In each iteration, we check if it's possible to complete all jobs within the guessed time by iterating through all the jobs, where n is the number of jobs. Thus, each check takes O(n) time. Therefore, the overall time complexity is O(n log s).

Space Complexity

O(1) – The algorithm primarily uses binary search and a feasibility check. The binary search only requires storing a few variables to track the start, end, and middle points of the search range. The feasibility check, involving greedy job assignment, operates in place or utilizes a few integer variables to track worker load and assigned jobs. Thus, the auxiliary space used is constant regardless of the number of jobs (N), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty jobs array	Return 0 immediately as there are no jobs to process.
Single job in the array	Assign the single job to one worker, and the minimum time is the job's duration.
Jobs array with all zero durations	The minimum time is 0 since all jobs complete instantly regardless of worker assignments.
Large number of jobs and limited workers	The binary search range must be appropriately defined to avoid potential integer overflow issues during mid calculation.
Jobs array with very large job durations	Integer overflow must be considered when summing job durations; using long data types can prevent this.
Number of workers is greater than or equal to the number of jobs	The minimum time is equal to the duration of the longest job.
Input contains negative job durations	Throw an IllegalArgumentException as job durations cannot be negative.
Maximum integer value for the duration of one or more jobs	Handle possible integer overflows during the calculation of the total duration and the binary search mid-point.

Empty jobs array

How to Handle:

Return 0 immediately as there are no jobs to process.

Single job in the array

How to Handle:

Assign the single job to one worker, and the minimum time is the job's duration.

Jobs array with all zero durations

How to Handle:

The minimum time is 0 since all jobs complete instantly regardless of worker assignments.

Large number of jobs and limited workers

How to Handle:

The binary search range must be appropriately defined to avoid potential integer overflow issues during mid calculation.

Jobs array with very large job durations

How to Handle:

Integer overflow must be considered when summing job durations; using long data types can prevent this.

Number of workers is greater than or equal to the number of jobs

How to Handle:

The minimum time is equal to the duration of the longest job.

Input contains negative job durations

How to Handle:

Throw an IllegalArgumentException as job durations cannot be negative.

Maximum integer value for the duration of one or more jobs

How to Handle:

Handle possible integer overflows during the calculation of the total duration and the binary search mid-point.

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:

What is the range of values for the time each job takes?
Can any job have a time of 0?
Are there any constraints on the number of workers available?
If it's impossible to complete all jobs within any finite time, what should I return?
Is the input list of jobs guaranteed to be non-empty?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each job one by one.
For each job, explore all possible workers that it could be assigned to.
For each worker that a job can be assigned to, calculate how long that worker would take to complete all their assigned jobs, including the new one.
Consider every combination of job-to-worker assignments. This will result in a lot of different ways the work could be divided.
For each possible division of work, find the worker who takes the longest amount of time to complete all of their assigned jobs. This is the total time it would take to complete all the jobs under that particular division.
Compare the total time for all the different divisions of work. Keep track of the shortest total time you find.
After considering every single possible way to divide the jobs among the workers, the shortest total time you kept track of will be the minimum time to finish all jobs.

Code Implementation

def find_minimum_time_to_finish_all_jobs(job_durations, number_of_workers):
    minimum_time = float('inf')

    def calculate_minimum_time_recursive(index, worker_assignments):
        nonlocal minimum_time

        # Base case: all jobs have been assigned
        if index == len(job_durations):
            maximum_worker_time = 0
            for worker_index in range(number_of_workers):
                maximum_worker_time = max(maximum_worker_time, sum(worker_assignments[worker_index]))
            minimum_time = min(minimum_time, maximum_worker_time)
            return

        # Try assigning the current job to each worker
        for worker_index in range(number_of_workers):
            # Create a new assignment configuration
            new_worker_assignments = [worker_assignments[i][:] for i in range(number_of_workers)]
            new_worker_assignments[worker_index].append(job_durations[index])

            # Recursively explore the next job assignment
            calculate_minimum_time_recursive(index + 1, new_worker_assignments)

    # Initialize worker assignments as empty lists for each worker
    initial_worker_assignments = [[] for _ in range(number_of_workers)]

    # Start the recursive process
    calculate_minimum_time_recursive(0, initial_worker_assignments)

    return minimum_time

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, recognize that the minimum possible time is at least as long as the single longest job. Also, the maximum possible time is no longer than the sum of all the jobs.
Now, use binary search within this range of possible completion times. Pick a time in the middle of the range as your guess.
For the current guess, determine if it is possible for a given number of workers to complete all jobs within the time. The key is to greedily assign jobs to each worker until they are full, and move on to the next worker if needed.
If it is possible to complete all jobs within the guess, try a smaller guess. If it's not possible, you will need a larger guess.
Repeat this binary search process of guessing and checking, narrowing the search range, until you find the smallest possible time that allows all jobs to be completed. This will be the minimum completion time.

Code Implementation

def find_minimum_time_to_finish_all_jobs(jobs, number_of_workers):
    start_time = max(jobs)
    end_time = sum(jobs)

    while start_time < end_time:
        mid_time = (start_time + end_time) // 2

        # Check if it's possible to complete within mid_time
        if is_possible_to_complete(jobs, number_of_workers, mid_time):
            end_time = mid_time
        else:
            start_time = mid_time + 1

    return start_time

def is_possible_to_complete(jobs, number_of_workers, max_time_per_worker):
    workers_needed = 1
    current_worker_time = 0

    # Iterate through each job and assign to worker greedily
    for job_duration in jobs:
        if job_duration > max_time_per_worker:
            return False

        if current_worker_time + job_duration <= max_time_per_worker:
            current_worker_time += job_duration
        else:
            # Need a new worker if current can't complete the job.
            workers_needed += 1
            current_worker_time = job_duration

    # If the needed workers exceed the number, not possible.
    if workers_needed <= number_of_workers:
        return True
    else:
        return False

# The is_possible_to_complete checks if a completion time is feasible.
# Based on this result, we adjust the search space

# Binary search to find the minimum completion time.
# We want to find the smallest time all the jobs can be completed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty jobs array	Return 0 immediately as there are no jobs to process.
Single job in the array	Assign the single job to one worker, and the minimum time is the job's duration.
Jobs array with all zero durations	The minimum time is 0 since all jobs complete instantly regardless of worker assignments.
Large number of jobs and limited workers	The binary search range must be appropriately defined to avoid potential integer overflow issues during mid calculation.
Jobs array with very large job durations	Integer overflow must be considered when summing job durations; using long data types can prevent this.
Number of workers is greater than or equal to the number of jobs	The minimum time is equal to the duration of the longest job.
Input contains negative job durations	Throw an IllegalArgumentException as job durations cannot be negative.
Maximum integer value for the duration of one or more jobs	Handle possible integer overflows during the calculation of the total duration and the binary search mid-point.

Empty jobs array

How to Handle:

Return 0 immediately as there are no jobs to process.

Single job in the array

How to Handle:

Assign the single job to one worker, and the minimum time is the job's duration.

Jobs array with all zero durations

How to Handle:

The minimum time is 0 since all jobs complete instantly regardless of worker assignments.

Large number of jobs and limited workers

How to Handle:

The binary search range must be appropriately defined to avoid potential integer overflow issues during mid calculation.

Jobs array with very large job durations

How to Handle:

Integer overflow must be considered when summing job durations; using long data types can prevent this.

Number of workers is greater than or equal to the number of jobs

How to Handle:

The minimum time is equal to the duration of the longest job.

Input contains negative job durations

How to Handle:

Throw an IllegalArgumentException as job durations cannot be negative.

Maximum integer value for the duration of one or more jobs

How to Handle:

Handle possible integer overflows during the calculation of the total duration and the binary search mid-point.