Find Minimum Time to Finish All Jobs II — LeetCode 2323 Python Solution

The problem

You are given two 0-indexed integer arrays jobs and workers of equal length, where jobs[i] is the amount of time needed to complete the ith job, and workers[j] is the amount of time the jth worker can work each day. Each job should be assigned to exactly one worker, such that each worker completes exactly one job.

Example

Input

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

Output

2

Explanation

- Assign the 2nd worker to the 0th job. It takes them 1 day to finish the job.

Python solution

class Solution:
    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:
        jobs.sort()
        workers.sort()
        return max((a + b - 1) // b for a, b in zip(jobs, workers))

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2323. Find Minimum Time to Finish All Jobs II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems