Find Minimum Time to Finish All Jobs II

To solve this problem, we can use a binary search approach to determine the minimum number of days required to complete all jobs. The main idea is to set a range of possible days, and for each possible number of days, we’ll check if it’s possible to finish the tasks in that many days.

Steps:

  1. Sort both jobs and workers in descending order.
  2. Define the binary search range from 1 to the maximum job time.
  3. For each possible number of days, try to match the jobs and workers to see if all jobs can be finished within the given days.

The main part of the solution is to check if a given number of days is feasible. For this, we can try to match the longest job with the fastest worker, then move on to the next job and worker, ensuring that each worker’s work doesn’t exceed the given number of days.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:
        def canFinish(days: int) -> bool:
            jobIdx, workerIdx = 0, 0
            while jobIdx < len(jobs) and workerIdx < len(workers):
                if jobs[jobIdx] <= workers[workerIdx] * days:
                    jobIdx += 1
                workerIdx += 1
            return jobIdx == len(jobs)

        jobs.sort(reverse=True)
        workers.sort(reverse=True)

        left, right = 1, max(jobs)
        while left < right:
            mid = (left + right) // 2
            if canFinish(mid):
                right = mid
            else:
                left = mid + 1

        return left

This solution first sorts both jobs and workers in descending order to match the longest jobs with the fastest workers. The binary search is then performed to find the minimum number of days, and for each possible number of days, the canFinish function checks if it’s feasible to finish all jobs within those days. The final result is the minimum number of days required to complete all jobs.