Find Minimum Time To Finish All Jobs Ii - Leetcode Solution

Problem:

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the ith job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to minimize the maximum working time among all workers.

Return the minimum possible maximum working time of any assignment.

Solution:

This problem can be solved using binary search. The idea is to find the minimum possible maximum working time among all workers. We can start with the minimum time which is the maximum time it takes to complete any job, and the maximum time which is the total sum of all job times.

For each mid value of the range, we can assign jobs to workers greedily, i.e., we assign each job to the worker who has the least amount of working time so far. If at any point, the working time of any worker exceeds the mid value, we stop and try to assign the remaining jobs to the next worker.

If we can successfully assign all jobs within the mid value, we try with a smaller mid value to see if we can find a better solution. Otherwise, we try with a larger mid value.

We keep doing this until the left and right boundaries of the range converge to a single value, which will be the minimum possible maximum working time.

Here is the Python code:

class Solution: def minimumTimeRequired(self, jobs: List[int], k: int) -> int:

    def possible(mid, jobs, k):
        workers = [0] * k
        for j in jobs:
            i = 0
            while i < k and workers[i] + j > mid:
                i += 1
            if i == k:
                return False
            workers[i] += j
        return True
    
    jobs.sort(reverse=True)
    left, right = jobs[0], sum(jobs)
    
    while left < right:
        mid = (left + right) // 2
        if possible(mid, jobs, k):
            right = mid
        else:
            left = mid + 1
    
    return left

Time Complexity: O(n log m), where n is the number of jobs and m is the maximum possible working time. The binary search takes log m time, and the possible function takes n time.

Space Complexity: O(1), constant extra space is used.

1