Find Minimum Time to Finish All Jobs

hard backtracking bitmask optimization

Problem

You are given an array jobs where jobs[i] is the time to finish job i, and k workers. Every job must be assigned to exactly one worker. A worker’s working time is the sum of their assigned jobs. Find an assignment that minimizes the maximum working time of any worker, and return that minimum possible maximum.

Inputjobs = [1,2,4,7,8], k = 2

Output11

Worker 1 takes {1, 2, 8} = 11 and worker 2 takes {4, 7} = 11, so the maximum working time is 11 — the smallest achievable.

jobs (comma-separated)

k (workers)

def minimumTimeRequired(jobs, k):
    jobs.sort(reverse=True)          # big jobs first prunes faster
    n = len(jobs)
    loads = [0] * k                  # working time of each worker
    best = sum(jobs)                 # upper bound: all jobs on one worker

    def dfs(i):
        nonlocal best
        if i == n:                   # every job placed
            best = min(best, max(loads))
            return
        seen = set()
        for w in range(k):
            if loads[w] in seen:     # skip identical worker states
                continue
            if loads[w] + jobs[i] >= best:
                continue             # cannot beat best, prune
            seen.add(loads[w])
            loads[w] += jobs[i]      # assign job i to worker w
            dfs(i + 1)
            loads[w] -= jobs[i]      # undo (backtrack)
            if loads[w] == 0:        # worker was empty: stop trying
                break
    dfs(0)
    return best

function minimumTimeRequired(jobs, k) {
  jobs.sort((a, b) => b - a);            // big jobs first prunes faster
  const n = jobs.length;
  const loads = new Array(k).fill(0);    // working time of each worker
  let best = jobs.reduce((s, x) => s + x, 0); // all on one worker

  function dfs(i) {
    if (i === n) {                       // every job placed
      best = Math.min(best, Math.max(...loads));
      return;
    }
    const seen = new Set();
    for (let w = 0; w < k; w++) {
      if (seen.has(loads[w])) continue;  // skip identical worker states
      if (loads[w] + jobs[i] >= best) continue; // prune
      seen.add(loads[w]);
      loads[w] += jobs[i];               // assign job i to worker w
      dfs(i + 1);
      loads[w] -= jobs[i];               // undo (backtrack)
      if (loads[w] === 0) break;         // worker was empty: stop
    }
  }
  dfs(0);
  return best;
}

int best;
int minimumTimeRequired(int[] jobs, int k) {
    Arrays.sort(jobs);                       // ascending, then reverse
    for (int l = 0, r = jobs.length - 1; l < r; l++, r--) {
        int t = jobs[l]; jobs[l] = jobs[r]; jobs[r] = t; // big jobs first prunes faster
    }
    int[] loads = new int[k];                // working time of each worker
    best = 0; for (int j : jobs) best += j;  // all on one worker
    dfs(jobs, 0, loads);
    return best;
}
void dfs(int[] jobs, int i, int[] loads) {
    if (i == jobs.length) {                  // every job placed
        int mx = 0; for (int l : loads) mx = Math.max(mx, l);
        best = Math.min(best, mx);
        return;
    }
    Set<Integer> seen = new HashSet<>();
    for (int w = 0; w < loads.length; w++) {
        if (!seen.add(loads[w])) continue;   // skip identical states
        if (loads[w] + jobs[i] >= best) continue; // prune
        loads[w] += jobs[i];                 // assign job i to worker w
        dfs(jobs, i + 1, loads);
        loads[w] -= jobs[i];                 // undo (backtrack)
        if (loads[w] == 0) break;            // worker was empty: stop
    }
}

int best;
void dfs(vector<int>& jobs, int i, vector<int>& loads) {
    if (i == (int)jobs.size()) {             // every job placed
        best = min(best, *max_element(loads.begin(), loads.end()));
        return;
    }
    set<int> seen;
    for (int w = 0; w < (int)loads.size(); w++) {
        if (seen.count(loads[w])) continue;  // skip identical states
        if (loads[w] + jobs[i] >= best) continue; // prune
        seen.insert(loads[w]);
        loads[w] += jobs[i];                 // assign job i to worker w
        dfs(jobs, i + 1, loads);
        loads[w] -= jobs[i];                 // undo (backtrack)
        if (loads[w] == 0) break;            // worker was empty: stop
    }
}
int minimumTimeRequired(vector<int>& jobs, int k) {
    sort(jobs.rbegin(), jobs.rend());        // big jobs first prunes faster
    vector<int> loads(k, 0);
    best = accumulate(jobs.begin(), jobs.end(), 0);
    dfs(jobs, 0, loads);
    return best;
}

Explanation

This is an optimization by backtracking problem. Because jobs.length ≤ 12, we can afford to search over assignments — but only if we prune aggressively, otherwise kⁿ blows up.

We keep an array loads, one running total per worker. The recursion dfs(i) places job i into some worker, then recurses on job i + 1. When all jobs are placed we update best with the largest worker load of this complete assignment.

Three pruning tricks make it fast. (1) Sort jobs descending so the heavy jobs are committed early — bad branches blow past best sooner. (2) Prune by bound: if putting job i on worker w already makes that worker reach best or more, skip it — it can never beat the current answer. (3) Symmetry breaking: within one call, if two workers currently have the same load, trying both is redundant, so we use a seen set; and if a worker is empty (load == 0), placing job i there is equivalent to every other empty worker, so we break.

Example: jobs = [1,2,4,7,8], k = 2. Sorted descending it is [8,7,4,2,1]. The optimal split groups {8,2,1} and {7,4}, both summing to 11, so the answer is 11.

Time: O(kⁿ) worst case, far less with pruning Space: O(n + k)