1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 107

Solution

Method 1 – Backtracking with Pruning

Intuition

Try all possible assignments of jobs to workers, but prune branches where the current assignment already exceeds the best found so far. Assign larger jobs first to maximize pruning.

Approach

Sort jobs in descending order.
Use a recursive function to assign each job to a worker.
Track the maximum working time among all workers.
Prune branches where the current max time is already worse than the best answer.
Return the minimum possible maximum time.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int ans = INT_MAX;\n    void dfs(vector<int>& jobs, vector<int>& workers, int idx, int k) {\n        if (idx == jobs.size()) {\n            ans = min(ans, *max_element(workers.begin(), workers.end()));\n            return;\n        }\n        for (int i = 0; i < k; ++i) {\n            workers[i] += jobs[idx];\n            int cur = *max_element(workers.begin(), workers.end());\n            if (cur < ans)\n                dfs(jobs, workers, idx + 1, k);\n            workers[i] -= jobs[idx];\n            if (workers[i] == 0) break;\n        }\n    }\n    int minimumTimeRequired(vector<int>& jobs, int k) {\n        sort(jobs.rbegin(), jobs.rend());\n        vector<int> workers(k);\n        dfs(jobs, workers, 0, k);\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> ans </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> INT_MAX;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    void</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> dfs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> jobs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span>&#

Related Tags