LeetCode1723(2021.5.8)

LC1723. 完成所有工作的最短时间

class Solution {
public:
    int res = 0x3f3f3f3f;

    void dfs(vector<int> jobs, int i, vector<int>worker, int maxi){
        if (i == jobs.size()) {
            res = min(res, maxi);
            return;
        }
        set<int> st;
        for (int j = 0; j < worker.size(); ++j) {
            if (st.find(worker[j]) != st.end()) continue;
            st.insert(worker[j]);
            if (worker[j] + jobs[i] >= res) continue;
            worker[j] += jobs[i];
            dfs(jobs, i + 1, worker, max(worker[j], maxi));
            worker[j] -= jobs[i];
        }
    }

    int minimumTimeRequired(vector<int>& jobs, int k) {
        vector<int> x(k);
        dfs(jobs, 0, x, 0);
        return res;
    }
};

发表评论