Krammer's blog

https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/ from Google

Thinking process:

The concept for this is actually simple. We can use a bitmap to represent what jobs have been done. dp[i][j] means the minimum Hamming when first i person finishing jobs represented by j. Since there’s only 12 jobs, j will be less than 4096. To calculate dp[i][j], we check every possible subset l in j, and delegate l to person i, which means that first i-1 person should complete j-l jobs, which is dp[i-1][j-l].

We use another cache called dp2 to cache the working time for each l so that we don’t need to compute the time again and again.

Here is the code.

 1class Solution {
 2public:
 3    vector<int> j;
 4    vector<int> dp2;
 5    int N;
 6    int dp[12][4096];
 7    int calTime(int x) {
 8        if (dp2[x] != INT_MAX) return dp2[x];
 9        int ret = 0;
10        for (int i=0; i<N; i++) {
11            if (x & (1<<i)) ret += j[i];
12        }
13        return dp2[x] = ret;
14    }
15    int minimumTimeRequired(vector<int>& jobs, int k) {
16        N = jobs.size();
17        j = jobs;
18        for (int i=0; i<12; i++) for (int j=0; j<4096; j++) dp[i][j] = INT_MAX;
19        dp2.resize(1<<N, INT_MAX);
20        for (int i=1; i<(1<<N); i++) {
21            dp[0][i] = calTime(i);
22        }
23        for (int i=1; i<k; i++) {
24            for (int j=1; j<(1<<N); j++) {
25                for (int l=j; l>0; l=j&(l-1)) {
26                    dp[i][j] = min(dp[i][j], max(calTime(l), dp[i-1][j-l]));
27                }
28            }
29        }
30        return dp[k-1][(1<<N)-1];
31    }
32};

Editorial: LeetCode 1723 Find Minimum Time to Finish All Jobs