LeetCode 1723. Find Minimum Time to Finish All Jobs

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.begin(), jobs.end());
        int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0);
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    bool check(vector<int>& jobs, int k, int limit) {
        vector<int> workloads(k);
        return backtrack(jobs, workloads, 0, limit);
    }
    bool backtrack(vector<int>& jobs, vector<int>& workloads, int idx, int limit){
        if (idx == jobs.size()) {
            return true;
        }
        int curr = jobs[idx];
        for (auto& workload : workloads) {
            workload += curr;
            if (workload <= limit && backtrack(jobs, workloads, idx + 1, limit)) {
                return true;
            }
            workload -= curr;
            if (workload == 0 || workload + curr == limit) {
                break;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size(), sz = 1 << n;
        vector<int> sum(sz);
        for (int i = 1; i < sz; i++) {
            int x = __builtin_ctz(i), y = i - (1 << x);
            sum[i] = sum[y] + jobs[x];
        }
        vector<vector<int>> f(k, vector<int>(sz));
        f[0] = vector<int>(sum.begin(), sum.end());
        for (int i = 1; i < k; i++) {
            for (int j = 0; j < sz; j++) {
                int minn = INT_MAX;
                for (int x = j; x; x = (x - 1) & j) {
                    minn = min(minn, max(f[i - 1][j - x], sum[x]));
                }
                f[i][j] = minn;
            }
        }
        return f[k - 1][sz - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size(), sz = 1 << n;
        vector<int> s(sz);
        for (int i = 1; i < sz; ++i) {
            int x = __builtin_ctz(i), y = i - (1 << x);
            s[i] = s[y] + jobs[x];
        }
        vector<int> f(s.begin(), s.end());
        for (int i = 1; i < k; ++i) {
            for (int j = sz - 1; j >= 0; --j) {
                int minn = INT_MAX;
                for (int x = j; x; x = (x - 1) & j) {
                    minn = min(minn, max(f[j - x], s[x]));
                }
                f[j] = minn;
            }
        }
        return f[sz - 1];
    }
};