Find Minimum Time To Finish All Jobs - Leetcode Solution

Problem statement:

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.

Example 1:

Input: jobs = [3,2,3], k = 3 Output: 3 Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2 Output: 11 Explanation: Assign the jobs the following way: Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11) Worker 2: 4, 7 (working time = 4 + 7 = 11) The maximum working time is 11.

Solution:

This is a classic problem on binary search. We can use binary search to find the minimum possible maximum working time of any assignment.

The idea is to start with the range [0, sum(jobs)], where sum(jobs) is the sum of all jobs. Using binary search we can check if it is possible to assign the jobs such that the maximum working time is less than or equal to mid.

For this we can use depth first search (dfs) with backtracking. We can start by assigning the first job to the first worker. For each worker, we can try assigning the job to each of k workers. If the working time of the current worker does not exceed mid, we can continue the dfs for the next job. If the working time of the current worker exceeds mid, we can backtrack and try assigning the job to the next worker. If we have assigned all jobs, and the maximum working time is less than or equal to mid, we can update the result and continue the binary search using the lower half of the range. If the maximum working time is greater than mid, we can continue the binary search using the upper half of the range.

The time complexity of this algorithm is O(n log(sum(jobs))), where n is the number of jobs.

Code:

class Solution { public: bool dfs(vector<int>& jobs, vector<int>& workers, int k, int mid) { if (k == jobs.size()) return true; unordered_set<int> used; for (int i = 0; i < workers.size(); i++) { if (used.count(workers[i])) continue; if (workers[i] + jobs[k] <= mid) { used.insert(workers[i]); workers[i] += jobs[k]; if (dfs(jobs, workers, k + 1, mid)) return true; workers[i] -= jobs[k]; } } return false; }

int minimumTimeRequired(vector<int>& jobs, int k) {
    int l = 0, r = accumulate(jobs.begin(), jobs.end(), 0);
    while (l < r) {
        int mid = (l + r) / 2;
        vector<int> workers(k, 0);
        if (dfs(jobs, workers, 0, mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

};

1