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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Minimum Time to Finish All Jobs

Number: 1825

Difficulty: Hard

Paid? No

Companies: Amazon, PhonePe

Problem Description

Given an array of job durations and k workers, assign each job to exactly one worker. The working time of a worker is the sum of the jobs assigned to them, and the goal is to minimize the maximum working time across all workers. In other words, find the optimal assignment of jobs that minimizes the maximum load any worker has, and return that value.

Key Insights

  • Sort the jobs in descending order for stronger pruning during backtracking.
  • Use a DFS/backtracking approach to try assigning each job to a worker.
  • Prune paths where the current maximum load already exceeds the best found solution.
  • Avoid redundant assignments by skipping workers with identical workloads in the current recursion step.
  • The constraints (up to 12 jobs) allow an exponential backtracking solution.

Space and Time Complexity

Time Complexity: Worst-case exponential in the number of jobs, O(k^n) where n is the number of jobs, though pruning helps in practice. Space Complexity: O(n) due to recursion stack and additional space for storing worker workloads.

Solution

The solution uses a backtracking (DFS) algorithm:

  1. First, sort the jobs in descending order to assign larger jobs earlier.
  2. Use recursion to try assigning each job to each worker.
  3. Track the maximum load among workers after each assignment.
  4. Prune the recursive calls if:
    • The current maximum load exceeds the best (minimum) maximum load found so far.
    • A worker has the same workload as a previous worker, avoiding redundant state exploration.
  5. Update the best found assignment when all jobs are assigned.

This approach efficiently explores the assignment possibilities while using pruning to cut off branches that cannot lead to an improved answer.

Code Solutions

# Python solution using DFS backtracking
def minimumTimeRequired(jobs, k):
    # Sort jobs in descending order to optimize backtracking
    jobs.sort(reverse=True)
    n = len(jobs)
    best = float('inf')
    
    def dfs(i, workloads):
        nonlocal best
        # If all jobs have been assigned, update the best result
        if i == n:
            best = min(best, max(workloads))
            return
        # Choose current job for allocation
        cur_job = jobs[i]
        seen = set()  # used to avoid duplicate assignment 
        for j in range(k):
            # Skip redundant assignment if this workload has been tried
            if workloads[j] in seen:
                continue
            if workloads[j] + cur_job < best:
                seen.add(workloads[j])
                workloads[j] += cur_job  # assign job to worker j
                dfs(i + 1, workloads)    # move to the next job
                workloads[j] -= cur_job  # backtrack
            # If a worker hasn't been assigned any job, break to avoid symmetric cases
            if workloads[j] == 0:
                break

    dfs(0, [0] * k)
    return best

# Example usage
print(minimumTimeRequired([3,2,3], 3))
← Back to All Questions