Find Minimum Time to Finish All Jobs LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minimumTimeRequired(vector<int> &jobs, int k) {
4
    int sum = 0;
5
    for (int j : jobs) sum += j;
6
    sort(jobs.begin(), jobs.end(), greater<int>());
7
    int l = jobs[0], r = sum;
8
    while (l < r) {
9
      int mid = (l + r) >> 1;
10
      vector<int> worker(k, 0);
11
      if (dfs(jobs, worker, 0, mid))
12
        r = mid;
13
      else
14
        l = mid + 1;
15
    }
16
    return l;
17
  }
18
  bool dfs(vector<int> &jobs, vector<int> &worker, int step, int target) {
19
    if (step >= jobs.size()) return true;
20
    int cur = jobs[step];
21
    // assign cur to worker i
22
    for (int i = 0; i < worker.size(); i++) {
23
      if (worker[i] + cur <= target) {
24
        worker[i] += cur;
25
        if (dfs(jobs, worker, step + 1, target)) return true;
26
        worker[i] -= cur;
27
      }
28
      if (worker[i] == 0) break;
29
    }
30
    return false;
31
  }
32
};