LeetCode 2323 - Find Minimum Time to Finish All Jobs II

LeetCode Problem 2323

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

This problem asks us to assign jobs to workers in a way that minimizes the total number of days needed to finish all jobs.

We are given two integer arrays of equal length:

• jobs[i] represents the amount of work required for the i-th job.
• workers[j] represents how much work the j-th worker can complete in one day.

Each worker must be assigned exactly one job, and each job must be assigned to exactly one worker. Once a worker is assigned a job, the number of days required for that worker to finish the job is:

$$\lceil \frac{\text{job}}{\text{worker}} \rceil$$

This means if a worker can complete 5 units per day and the job requires 12 units, it takes:

$$\lceil 12/5 \rceil = 3$$

days.

The objective is to minimize the maximum number of days required among all assignments, because all workers operate independently and jobs finish when the slowest assignment finishes.

The constraints are important:

• n can be as large as 10^5
• Job sizes and worker capacities can also reach 10^5

Since n is large, any factorial or quadratic assignment strategy is far too slow. We need an algorithm around O(n log n) to comfortably handle the input size.

There are also several guarantees in the problem:

• The arrays always have equal length.
• Every worker and job has a positive value, so division-by-zero concerns do not exist.
• Every worker must receive exactly one job.

An important observation is that a poor assignment can dramatically increase the maximum completion time. For example, assigning the strongest worker to the easiest job and the weakest worker to the hardest job can create unnecessarily large completion times.

A few edge cases stand out immediately. If there is only one worker and one job, the answer is simply the ceiling division of that job by that worker. If all workers are equally strong, then only job ordering matters. If all jobs are identical, pairing choices still matter because weaker workers may become bottlenecks. Large mismatches between worker strength and job size can expose flaws in greedy reasoning.

Approaches

Brute Force Approach

A brute-force solution would try every possible assignment of workers to jobs.

Since each worker must be assigned exactly one unique job, this becomes a permutation problem. For every possible worker-job pairing configuration:

1. Compute the required days for each assigned pair.
2. Find the maximum days among those assignments.
3. Keep the minimum maximum value across all permutations.

This guarantees correctness because every valid assignment is examined.

However, the number of assignments is:

$$n!$$

For n = 10^5, this is astronomically large and completely infeasible.

Even for n = 15, brute force is already impractical.

Key Insight for an Optimal Solution

The key insight comes from a greedy matching principle.

Suppose we want to minimize the worst completion time. If we assign a very large job to a weak worker while a strong worker is handling an easy job, the weak worker becomes a bottleneck.

To reduce the maximum completion time, we should pair:

• smaller jobs with weaker workers
• larger jobs with stronger workers

This is an example of a greedy matching strategy similar to minimizing maximum pair cost.

We sort both arrays:

• Sort jobs in ascending order.
• Sort workers in ascending order.

Then pair elements at the same indices.

For each pair, compute:

$$\left\lceil \frac{\text{job}}{\text{worker}} \right\rceil$$

The answer is the maximum of these values.

Why does sorting work?

If two workers are out of order relative to job difficulty, swapping them cannot make the worst completion time larger, and often improves it. This is a classic exchange argument. Pairing strongest workers with hardest jobs minimizes imbalance.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n)	Tries every assignment permutation
Optimal Greedy + Sorting	O(n log n)	O(1) or O(log n)	Sort both arrays and pair corresponding elements

Algorithm Walkthrough

1. Sort the jobs array in ascending order.

We want smaller jobs to appear first and larger jobs later. This creates a natural progression of difficulty. 2. Sort the workers array in ascending order.

This places weaker workers first and stronger workers later. 3. Pair jobs and workers at the same index.

The weakest worker receives the smallest job, the second weakest worker receives the second smallest job, and so on. 4. For each pair, compute the required number of days.

Since a worker may not perfectly divide the job size, we use ceiling division:

$$\left\lceil \frac{job}{worker} \right\rceil$$

In integer arithmetic:

(job + worker - 1) // worker

This avoids floating-point precision issues. 5. Track the maximum number of days.

Since all jobs run independently, total completion time is determined by the slowest assignment. 6. Return the maximum value found.

Why it works

The correctness comes from a greedy exchange argument. If a larger job is assigned to a weaker worker while a smaller job is assigned to a stronger worker, swapping those assignments cannot increase the maximum completion time. Repeatedly applying this reasoning leads to an arrangement where jobs and workers are both sorted and paired in order. This minimizes the worst-case completion time across all assignments.

Python Solution

from typing import List

class Solution:
    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:
        jobs.sort()
        workers.sort()

        minimum_days = 0

        for job, worker in zip(jobs, workers):
            days_needed = (job + worker - 1) // worker
            minimum_days = max(minimum_days, days_needed)

        return minimum_days

The implementation begins by sorting both arrays. This establishes the optimal pairing order where weaker workers receive smaller jobs and stronger workers receive larger jobs.

After sorting, we iterate through both arrays simultaneously using zip. For every (job, worker) pair, we calculate the number of days needed using ceiling division:

(job + worker - 1) // worker

This formula correctly computes the ceiling without floating-point arithmetic.

We continuously track the largest number of days because the overall completion time is determined by the slowest worker-job assignment. Finally, we return that maximum.

Go Solution

package main

import "sort"

func minimumTime(jobs []int, workers []int) int {
	sort.Ints(jobs)
	sort.Ints(workers)

	maxDays := 0

	for i := 0; i < len(jobs); i++ {
		daysNeeded := (jobs[i] + workers[i] - 1) / workers[i]

		if daysNeeded > maxDays {
			maxDays = daysNeeded
		}
	}

	return maxDays
}

The Go implementation follows exactly the same logic as the Python version. We sort both slices using sort.Ints, iterate through matching indices, compute ceiling division using integer arithmetic, and maintain the maximum value.

Go does not require special handling for integer overflow here because the constraints are small enough. The maximum intermediate value is at most:

$$10^5 + 10^5 - 1$$

which easily fits inside Go's int type.

Since slices are modified in place, the original ordering is overwritten, just like Python's in-place .sort().

Worked Examples

Example 1

Input:

jobs = [5,2,4]
workers = [1,7,5]

Step 1: Sort both arrays

Array	Result
jobs	[2, 4, 5]
workers	[1, 5, 7]

Step 2: Pair and compute days

Job	Worker	Calculation	Days	Current Maximum
2	1	ceil(2/1)	2	2
4	5	ceil(4/5)	1	2
5	7	ceil(5/7)	1	2

Final answer:

2

Example 2

Input:

jobs = [3,18,15,9]
workers = [6,5,1,3]

Step 1: Sort both arrays

Array	Result
jobs	[3, 9, 15, 18]
workers	[1, 3, 5, 6]

Step 2: Pair and compute days

Job	Worker	Calculation	Days	Current Maximum
3	1	ceil(3/1)	3	3
9	3	ceil(9/3)	3	3
15	5	ceil(15/5)	3	3
18	6	ceil(18/6)	3	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting both arrays dominates runtime
Space	O(1) or O(log n)	Sorting is in place, recursion stack may be used internally

The dominant operation is sorting the two arrays, which takes O(n log n) time. The final traversal to compute the maximum completion time is linear, O(n).

Space complexity is effectively constant if we ignore sorting internals. However, practical sorting algorithms may use logarithmic recursion stack space.

Test Cases

solution = Solution()

assert solution.minimumTime([5, 2, 4], [1, 7, 5]) == 2  # Example 1
assert solution.minimumTime([3, 18, 15, 9], [6, 5, 1, 3]) == 3  # Example 2

assert solution.minimumTime([10], [2]) == 5  # Single worker/job
assert solution.minimumTime([1], [100]) == 1  # Worker stronger than job

assert solution.minimumTime([5, 5, 5], [5, 5, 5]) == 1  # Equal jobs/workers
assert solution.minimumTime([10, 10, 10], [1, 2, 10]) == 5  # Mixed worker strengths

assert solution.minimumTime([100000], [1]) == 100000  # Maximum job size
assert solution.minimumTime([1, 100000], [1, 100000]) == 1  # Perfect matching

assert solution.minimumTime([8, 16, 24], [2, 4, 8]) == 4  # Increasing scale
assert solution.minimumTime([9, 1, 4], [3, 10, 2]) == 2  # Unsorted inputs

Test	Why
[5,2,4], [1,7,5]	Validates Example 1
[3,18,15,9], [6,5,1,3]	Validates Example 2
[10], [2]	Minimum input size
[1], [100]	Worker stronger than required
[5,5,5], [5,5,5]	Uniform values
[10,10,10], [1,2,10]	Different worker capacities
[100000], [1]	Maximum constraint value
[1,100000], [1,100000]	Perfectly balanced matching
[8,16,24], [2,4,8]	Scaling behavior
[9,1,4], [3,10,2]	Confirms sorting is necessary

Edge Cases

One important edge case is when there is only a single job and worker. A naive implementation might overcomplicate the logic or mishandle indexing. Since the arrays always have equal length, our implementation naturally handles this case because sorting a single-element array changes nothing, and the loop executes exactly once.

Another important edge case occurs when workers are significantly stronger than the assigned jobs. For example, jobs = [1, 2, 3] and workers = [100, 100, 100]. Integer division can be a source of bugs here because standard division would incorrectly produce 0 if floor division were used directly. Our ceiling division formula ensures every nonzero job takes at least one day.

A third important edge case is highly imbalanced worker strength. Consider jobs = [10, 10, 10] and workers = [1, 2, 100]. A poor assignment strategy could pair the strongest worker with an easy job and leave the weakest worker overloaded, increasing the maximum completion time. Sorting guarantees balanced matching, minimizing bottlenecks.

Finally, unsorted input is an important practical case. The problem does not guarantee any ordering for either array. Since our implementation explicitly sorts both arrays before pairing, it always computes the optimal assignment regardless of input order.