Problem Description

You have two arrays of equal length: jobs and workers. Each element jobs[i] represents the time needed to complete the i-th job, and each element workers[j] represents how many hours per day the j-th worker can work.

You need to assign each job to exactly one worker, with the constraint that:

• Each job must be assigned to exactly one worker
• Each worker must be assigned exactly one job

When a worker is assigned a job, they will work on it for their daily working hours until the job is complete. For example, if a job requires 10 hours and a worker can work 3 hours per day, it will take ⌈10/3⌉ = 4 days to complete.

The goal is to find an assignment that minimizes the maximum number of days any worker needs to complete their assigned job. This represents the total time needed to complete all jobs (since workers work in parallel).

The solution uses a greedy approach: sort both arrays and match them by index (smallest job to smallest capacity worker, etc.). Then calculate the days needed for each pair as ⌈jobs[i] / workers[i]⌉ and return the maximum among all pairs.

Intuition

The key insight is understanding what determines the total completion time. Since all workers work in parallel, the total time is determined by the worker who takes the longest to finish their job.

Consider what happens with different assignment strategies. If we assign a very long job to a worker with low daily capacity, that worker will take many days to complete it. Conversely, if we assign short jobs to workers with high capacity, they'll finish quickly but might be underutilized.

To minimize the maximum completion time, we want to avoid creating any particularly bad pairings. The worst case would be pairing the longest job with the slowest worker - this would create a bottleneck that determines the overall completion time.

This leads us to think about balance: we should match longer jobs with workers who have higher daily capacity, and shorter jobs with workers who have lower daily capacity. This way, the completion times across all worker-job pairs tend to be more uniform, avoiding extreme outliers.

Why does sorting and matching by index work? When both arrays are sorted, we're essentially creating a balanced assignment where:

• The hardest job goes to the most capable worker
• The easiest job goes to the least capable worker
• Everything in between follows this pattern

This greedy matching ensures no single worker-job pair becomes an excessive bottleneck. The formula (jobs[i] + workers[i] - 1) // workers[i] calculates the ceiling of the division, giving us the exact number of days needed for each pairing, and we return the maximum among all pairs since that determines when all jobs are complete.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy strategy with these steps:

Step 1: Sort both arrays

jobs.sort()
workers.sort()

By sorting both jobs and workers in ascending order, we prepare them for optimal pairing. After sorting:

• jobs[0] is the shortest job, jobs[-1] is the longest
• workers[0] has the lowest daily capacity, workers[-1] has the highest

Step 2: Pair jobs with workers by index

zip(jobs, workers)

The zip function pairs elements at the same index from both sorted arrays. This creates the balanced assignment where:

• jobs[0] (shortest) → workers[0] (lowest capacity)
• jobs[1] → workers[1]
• ...
• jobs[n-1] (longest) → workers[n-1] (highest capacity)

Step 3: Calculate days needed for each pair

(a + b - 1) // b

For each job-worker pair (a, b) where a is the job time and b is the worker's daily capacity, we calculate the number of days needed. The expression (a + b - 1) // b computes the ceiling of a/b using integer arithmetic:

• This is equivalent to math.ceil(a/b)
• It calculates how many full days of work are needed to complete job a at rate b per day

Step 4: Return the maximum days

max(...)

Since all workers work in parallel, the total completion time is determined by the worker who takes the longest. We return the maximum number of days among all worker-job pairs.

The time complexity is O(n log n) due to sorting, where n is the length of the arrays. The space complexity is O(1) if we don't count the space used for sorting.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• jobs = [5, 2, 4] (hours needed for each job)
• workers = [1, 7, 5] (hours per day each worker can work)

Step 1: Sort both arrays

• After sorting: jobs = [2, 4, 5]
• After sorting: workers = [1, 5, 7]

Step 2: Create paired assignments by index

• Job 0 (2 hours) → Worker 0 (1 hour/day)
• Job 1 (4 hours) → Worker 1 (5 hours/day)
• Job 2 (5 hours) → Worker 2 (7 hours/day)

Step 3: Calculate days needed for each pairing

• Worker 0 needs: ⌈2/1⌉ = 2 days
• Worker 1 needs: ⌈4/5⌉ = 1 day
• Worker 2 needs: ⌈5/7⌉ = 1 day

Using the formula (a + b - 1) // b:

• Worker 0: (2 + 1 - 1) // 1 = 2 // 1 = 2 days
• Worker 1: (4 + 5 - 1) // 5 = 8 // 5 = 1 day
• Worker 2: (5 + 7 - 1) // 7 = 11 // 7 = 1 day

Step 4: Find the maximum

• Maximum among [2, 1, 1] = 2 days

Result: The minimum possible maximum completion time is 2 days.

Notice how the greedy approach avoids bad pairings. If we had instead assigned the longest job (5 hours) to the slowest worker (1 hour/day), that would take 5 days - much worse than our optimal solution of 2 days.

Solution Implementation

Time and Space Complexity

The time complexity is O(n log n), where n is the number of jobs (which equals the number of workers based on the problem context). This complexity comes from:

• Sorting the jobs array: O(n log n)
• Sorting the workers array: O(n log n)
• The zip and max operations with the generator expression: O(n)
• Overall: O(n log n) + O(n log n) + O(n) = O(n log n)

The space complexity is O(log n). This comes from:

• The sorting operations use O(log n) space for the recursive call stack in typical implementations like Timsort (Python's default sorting algorithm)
• The generator expression ((a + b - 1) // b for a, b in zip(jobs, workers)) uses O(1) extra space as it doesn't create a list but generates values on-the-fly
• Overall: O(log n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Ceiling Division Formula

A common mistake is using regular integer division job_size // worker_speed instead of ceiling division. This would underestimate the days needed.

Wrong approach:

time_needed = job_size // worker_speed  # This rounds down!

Correct approach:

time_needed = (job_size + worker_speed - 1) // worker_speed
# OR
import math
time_needed = math.ceil(job_size / worker_speed)

2. Misunderstanding the Greedy Pairing Logic

Some might think pairing the largest job with the fastest worker (reverse pairing) would be optimal, but this can lead to suboptimal solutions.

Wrong pairing:

jobs.sort()
workers.sort(reverse=True)  # Wrong! This pairs smallest job with fastest worker

Why the correct pairing works: The balanced approach (small-to-small, large-to-large) prevents extreme mismatches. Consider:

• Jobs: [5, 10], Workers: [1, 10]
• Correct pairing: (5→1)=5 days, (10→10)=1 day, max=5 days
• Wrong pairing: (5→10)=1 day, (10→1)=10 days, max=10 days

3. Not Handling Edge Cases

Failing to consider when worker capacity is very large compared to job size.

Potential issue:

# If worker_speed > job_size, the result should be 1 day
# The formula (job_size + worker_speed - 1) // worker_speed handles this correctly

4. Using Float Division Unnecessarily

Using floating-point arithmetic when integer arithmetic suffices can introduce precision issues.

Less efficient:

import math
time_needed = int(math.ceil(float(job_size) / float(worker_speed)))

Better approach:

time_needed = (job_size + worker_speed - 1) // worker_speed

5. Modifying Input Arrays Without Consideration

The solution sorts the input arrays in-place, which modifies the original data. If the original order needs to be preserved elsewhere, create copies first.

Safe approach if original order matters:

jobs_sorted = sorted(jobs)
workers_sorted = sorted(workers)