We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Minimum Time to Finish All Jobs II

Number: 2458

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given two 0-indexed integer arrays jobs and workers of equal length, where jobs[i] is the amount of work required for the ith job and workers[j] denotes the amount of work a worker can do in one day, you need to assign each job to exactly one worker (and each worker must do exactly one job). When a worker j is assigned a job i, they take ceil(jobs[i] / workers[j]) days to complete it. All workers work concurrently, so the total time to finish all jobs is governed by the longest individual completion time. The goal is to determine the minimum number of days required such that there exists an assignment of jobs to workers where each can finish their assigned job within that number of days.

Key Insights

  • For a candidate number of days D, a worker with capacity w can finish any job with work requirement up to w * D.
  • Sort both the jobs and workers arrays; then, using a greedy assignment (two pointers), match the smallest available job to any worker who can complete it within D days.
  • Use binary search on D (ranging appropriately) to find the minimum valid D that allows all jobs to be assigned satisfying w * D >= job requirement.
  • The problem reduces to feasibility checking for a candidate D rather than directly finding an optimal assignment.

Space and Time Complexity

Time Complexity: O(n log M), where n is the length of the arrays and M is the maximum possible number of days (determined by the largest job and the smallest worker); the log M factor comes from the binary search. Space Complexity: O(n), primarily for sorting the arrays (if sorting in-place, the extra space might be O(1) or O(n) depending on the sort algorithm).

Solution

The solution uses a binary search to identify the smallest number of days D for which a valid assignment exists. For each candidate D, sort both jobs and workers in ascending order. Use a two-pointer technique to greedily assign each job to the first worker capable of completing it within D days (i.e. where worker capacity * D is at least the job requirement). If all jobs can be assigned under these conditions, then D is feasible. Adjust the binary search bounds accordingly until the minimum feasible D is found.

Code Solutions

# Python implementation with line-by-line comments
def minimum_days(jobs, workers):
    # Sort jobs and workers in ascending order
    jobs.sort()
    workers.sort()
    
    # Helper function to determine if all jobs can be completed in D days
    def can_finish(D):
        job_index = 0  # pointer for jobs array
        # Iterate through each worker
        for capacity in workers:
            # If current worker is capable of finishing the current job in D days, 
            # assign the job and move to the next job.
            if capacity * D >= jobs[job_index]:
                job_index += 1
                if job_index == len(jobs):  # all jobs assigned successfully
                    return True
        return False  # not all jobs could be assigned
    
    # Binary search range: minimum day is 1, maximum day is computed based on worst case pairing
    low, high = 1, max((job + workers[0] - 1) // workers[0] for job in jobs)
    
    while low < high:
        mid = (low + high) // 2
        if can_finish(mid):
            high = mid  # mid days are sufficient, try to find a smaller value
        else:
            low = mid + 1  # mid days are not sufficient, search higher
    return low

# Example usage:
print(minimum_days([5,2,4], [1,7,5]))  # Output: 2
print(minimum_days([3,18,15,9], [6,5,1,3]))  # Output: 3
← Back to All Questions