1723. minimum time to complete all work

Original link ：1723. The shortest time to complete all the work

 

solution:
        dfs + to flash back + prune

① The end condition : Task assignment completed ,maxt Save the maximum working hours of all workers , Reuse maxt And the previous maximum working hours res Compare , to update res.
② Allocate time , Depth-first search , Assign all tasks to the first person first , Go back and assign to the next person .
③ Pruning conditions 1： If the currently assigned worker hours are greater than the maximum worker hours at the end of the previous assignment , Pruning
④ Pruning conditions 2： If you go back , Working hours of workers workers[i] == 0, Pruning , Because the worker's later working hours are all 0, It makes no sense . 

class Solution {
public:
    int res = INT_MAX;
    int minimumTimeRequired(vector<int>& jobs, int k) {
        vector<int> workers (k, 0);   // Define the working hours of each worker 
        dfs(workers, jobs, 0);
        return res;
    }

    void dfs(vector<int> &workers,vector<int>& jobs,int index) {
        if(index == jobs.size()) {  // If all tasks are assigned , Updated once res
            int maxt = -1;
            for(int i = 0;i < workers.size();i++) { // Task assignment completed , Save maximum working time 
                maxt = max(maxt, workers[i]);
            }
            res = min(res, maxt);   // Update the minimum maximum working time 
            return;
        }

        for(int i = 0;i < workers.size();i++) {  // Allocate time 
            if(workers[i] + jobs[index] >= res) {   // If this assignment is greater than the previous minimum maximum working time , prune 
                continue;
            }
            workers[i] += jobs[index];
            dfs(workers,jobs,index + 1);
            workers[i] -= jobs[index];  // to flash back 

            if(workers[i] == 0) break;  // prune 
        }
    }
};