Find Minimum Time to Finish All Jobs II - Video Solutions

Problem Overview: You are given two arrays: jobs where jobs[i] represents the amount of work required for a job, and workers where workers[i] represents how much work a worker can complete per unit time. Each worker must take exactly one job. The goal is to assign jobs so the time when the last job finishes is minimized.

Approach 1: Brute Force Assignment (O(n!))

The direct idea is to try every possible assignment of workers to jobs and compute the finishing time for each configuration. For a pair (job, worker), the time required is ceil(job / worker). For each permutation, compute the maximum time across all pairs and keep the minimum across permutations. This guarantees the optimal assignment but quickly becomes infeasible since the number of permutations is n!. Space complexity is O(n) for recursion or permutation tracking. This approach only works for very small inputs and mainly demonstrates the assignment search space.

Approach 2: Binary Search on Time + Greedy Check (O(n log n + n log T))

Another idea is to guess the minimum finishing time using binary search. For a candidate time T, a worker can complete a job if worker[i] * T ≥ job[j]. Sort both arrays and greedily match workers to jobs while verifying whether all jobs can be finished within T. If feasible, try a smaller time; otherwise increase the bound. The sorting step dominates initially, while each feasibility check scans the arrays. Space complexity remains O(1) beyond sorting. This approach works but adds unnecessary complexity compared to the direct greedy observation.

Approach 3: Greedy Sorting (O(n log n))

The key insight: to minimize the maximum completion time, pair the largest job with the strongest worker. If a large job is assigned to a weak worker, the required time increases dramatically. Sorting both arrays ensures balanced assignments where stronger workers handle heavier jobs. After sorting, iterate once and compute time = ceil(jobs[i] / workers[i]) for each pair, tracking the maximum value. That maximum represents the time when the last job finishes. Sorting dominates the runtime with O(n log n) time and O(1) extra space (ignoring sort stack). This greedy pairing works because any swap that assigns a larger job to a weaker worker only increases the maximum completion time.

Relevant concepts include array manipulation, greedy decision making, and sorting strategies for optimal pairing.

Recommended for interviews: The greedy sorting approach is the expected solution. It shows you recognize the pairing strategy that minimizes the worst-case ratio. Mentioning the brute force assignment shows you understand the search space, but implementing the O(n log n) greedy solution demonstrates strong algorithmic reasoning.