Find Minimum Time to Finish All Jobs

Hard Dynamic Programming Bitmask DP Original on LeetCode

Reported atPinterestJuspay

Find Minimum Time to Finish All Jobs is a hard dynamic programming problem solved with the bitmask dp pattern. The best approach, optimal (binary search on the time + subset dp), runs in O(n · 2^n · log(sum)) time and O(2^n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every assignment) up.

Problem

You have an array jobs, where jobs[i] is how long the i-th job takes, and k workers. Every job must be given to exactly one worker, and a worker may get any number of jobs (including none). A worker’s working time is the sum of the lengths of its jobs.

Assign the jobs so that the largest working time among all workers is as small as possible, and return that value.

Examples

Example 1

Input
jobs = [4, 7, 2, 5], k = 2
Output
9
Why
One worker does 4 + 5 = 9 and the other 7 + 2 = 9, so both finish at time 9.

Example 2

Input
jobs = [6, 1, 1, 1], k = 3
Output
6
Why
The job of length 6 alone already takes 6, and the three short jobs fit easily on the other workers.

Example 3

Input
jobs = [3, 3, 3, 3, 3], k = 2
Output
9
Why
Five equal jobs over two workers: one worker must take three of them.

Constraints

  • 1 <= k <= jobs.length <= 12
  • 1 <= jobs[i] <= 10^7

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every assignment)O(k^n · k)O(n + k)
Better (backtracking with pruning)O(k^n) worst case, far less in practiceO(n + k)
Optimal (binary search on the time + subset DP)O(n · 2^n · log(sum))O(2^n)

1Brute force (try every assignment)

TimeO(k^n · k)Every job has k choices, and each leaf scans k loads.
SpaceO(n + k)Recursion depth n and the load array.

Give each job, one after another, to each of the k workers in turn. Every complete assignment is a leaf of the recursion; its working time is the largest worker load. Keep the smallest such value.

  1. Keep an array load of size k, all zeros.
  2. assign(i): if i == n, update best with max(load).
  3. Otherwise, for each worker w: add jobs[i] to load[w], recurse on i + 1, then undo.
class Solution {
    private int best;

    public int minimumTimeRequired(int[] jobs, int k) {
        best = Integer.MAX_VALUE;
        assign(jobs, 0, new int[k]);
        return best;
    }

    private void assign(int[] jobs, int i, int[] load) {
        if (i == jobs.length) {
            int mx = 0;
            for (int x : load) mx = Math.max(mx, x);
            best = Math.min(best, mx);
            return;
        }
        for (int w = 0; w < load.length; w++) {
            load[w] += jobs[i];
            assign(jobs, i + 1, load);
            load[w] -= jobs[i];
        }
    }
}

2Better (backtracking with pruning)

TimeO(k^n) worst case, far less in practicePruning does not change the worst-case bound, but the bound check and the empty-worker rule remove most symmetric and hopeless branches.
SpaceO(n + k)Recursion depth n and the load array.

Same search, but cut most branches. Place the longest jobs first so bad branches fail early. Skip a worker if giving it the job would already reach the best answer found. And when a job goes to a worker that was still empty, stop trying further workers: every other empty worker would produce the same situation.

  1. Sort jobs in decreasing order; best = sum of jobs + 1.
  2. assign(i, curMax): if i == n, best = curMax.
  3. For each worker w: skip it if load[w] + jobs[i] >= best; otherwise add, recurse with max(curMax, load[w]), undo.
  4. After undoing, if load[w] == 0, break (all remaining empty workers are equivalent).
class Solution {
    private int best;
    private int[] js;
    private int[] load;

    public int minimumTimeRequired(int[] jobs, int k) {
        js = jobs.clone();
        Arrays.sort(js);
        for (int l = 0, r = js.length - 1; l < r; l++, r--) {
            int t = js[l]; js[l] = js[r]; js[r] = t;
        }
        best = 1;
        for (int x : js) best += x;
        load = new int[k];
        assign(0, 0);
        return best;
    }

    private void assign(int i, int curMax) {
        if (i == js.length) {
            best = curMax;
            return;
        }
        for (int w = 0; w < load.length; w++) {
            if (load[w] + js[i] < best) {
                load[w] += js[i];
                assign(i + 1, Math.max(curMax, load[w]));
                load[w] -= js[i];
            }
            if (load[w] == 0) break;
        }
    }
}

3Optimal (binary search on the time + subset DP)

TimeO(n · 2^n · log(sum))Each feasibility test visits 2^n subsets and n jobs per subset; the binary search runs about log2(1.2 · 10^8) ≈ 27 times.
SpaceO(2^n)Two arrays indexed by subset.

If the jobs can be finished within time T, they can also be finished within any larger T, so binary-search the smallest feasible T between max(jobs) and sum(jobs). To test a T, process subsets of jobs: for every subset mask, store the best packing state as a pair (workers used, load on the current worker), compared lexicographically. Adding job j either fits on the current worker or opens a new worker that starts with j. T is feasible when the full set needs at most k workers.

  1. lo = max(jobs), hi = sum(jobs).
  2. feasible(T): cnt[0] = 1, cur[0] = 0. For each mask > 0 and each job j in mask, take the state of mask without j; if cur + jobs[j] <= T the new state is (cnt, cur + jobs[j]), else (cnt + 1, jobs[j]). Keep the lexicographically smallest state.
  3. Return cnt[full] <= k.
  4. Binary search: if feasible(mid) then hi = mid, else lo = mid + 1. Return lo.
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        int lo = 0, hi = 0;
        for (int x : jobs) {
            lo = Math.max(lo, x);
            hi += x;
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (feasible(jobs, k, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    private boolean feasible(int[] jobs, int k, int limit) {
        int n = jobs.length, full = (1 << n) - 1;
        int[] cnt = new int[full + 1];
        int[] cur = new int[full + 1];
        cnt[0] = 1;
        for (int mask = 1; mask <= full; mask++) {
            int bc = Integer.MAX_VALUE, bl = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0) continue;
                int prev = mask ^ (1 << j);
                int c = cnt[prev], l = cur[prev] + jobs[j];
                if (l > limit) {
                    c++;
                    l = jobs[j];
                }
                if (c < bc || (c == bc && l < bl)) {
                    bc = c;
                    bl = l;
                }
            }
            cnt[mask] = bc;
            cur[mask] = bl;
        }
        return cnt[full] <= k;
    }
}

Edge cases to test

  • k equal to the number of jobs (answer is the longest job)
  • k = 1 (answer is the sum of all jobs)
  • Many equal jobs, where symmetric assignments repeat the same work
  • One very long job that dominates the answer

Hints

Hint 1

With at most 12 jobs, exhaustive search is possible, but k^12 assignments is too many without pruning.

Hint 2

Turn the question around: given a time limit T, can the jobs be split into k groups that each sum to at most T? The answer is monotone in T, so binary search on T.

Hint 3

For a fixed T, a DP over subsets of jobs can track the fewest workers needed and the smallest load on the current worker.

FAQ

What is the best time complexity for Find Minimum Time to Finish All Jobs?

Optimal (binary search on the time + subset DP) runs in O(n · 2^n · log(sum)) time and O(2^n) extra space. Each feasibility test visits 2^n subsets and n jobs per subset; the binary search runs about log2(1.2 · 10^8) ≈ 27 times.

Which pattern does Find Minimum Time to Finish All Jobs use?

It is a dynamic programming problem that uses the bitmask dp pattern. Other problems with the same pattern: Optimal Account Balancing, Smallest Sufficient Team, Frequencies of Shortest Supersequences.

Is there a brute force solution for Find Minimum Time to Finish All Jobs?

Yes. Brute force (try every assignment) takes O(k^n · k) time and O(n + k) space. Give each job, one after another, to each of the k workers in turn.

Which edge cases should I test for Find Minimum Time to Finish All Jobs?

k equal to the number of jobs (answer is the longest job); k = 1 (answer is the sum of all jobs); Many equal jobs, where symmetric assignments repeat the same work; One very long job that dominates the answer.