LC.P1723[完成所有工作的最短时间]

方法一：回溯+剪枝(超时)

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
class Solution {
    int[] jobs;
    int n, k;
    int[] sum;
    int ans = Integer.MAX_VALUE;

    public int minimumTimeRequired(int[] jobs, int k) {
        this.jobs = jobs;
        this.k = k;
        this.n = jobs.length;
        sum = new int[n];
        dfs(0, 0);
        return ans;
    }

    /**
     * @param cur 当前处理到的工作
     * @param max 当前的最大工作时间
     */
    private void dfs(int cur, int max) {
        if (max >= ans) return;
        if (cur == n) {
            ans = max;
            return;
        }
        for (int i = 0; i < k; ++i) {
            sum[i] += jobs[cur];
            dfs(cur + 1, Math.max(max, sum[i]));
            sum[i] -= jobs[cur];
        }
    }
}
  • 时间复杂度：$O(k^n)$
  • 空间复杂度：$O(k)$

方法二：优化

方法一的分配方式是将每个任务依次分给每个工人，并递归此过程。

为达到最大剪枝效果，可优先将工作分配给空闲的工人

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
38
39
class Solution {
    int[] jobs;
    int n, k;
    int[] sum;
    int ans = Integer.MAX_VALUE;

    public int minimumTimeRequired(int[] jobs, int k) {
        this.jobs = jobs;
        this.k = k;
        this.n = jobs.length;
        sum = new int[n];
        dfs(0, 0, 0);
        return ans;
    }

    /**
     * @param cur  当前处理到的工作
     * @param used 当前分配给了多少个工人
     * @param max  当前的最大工作时间
     */
    private void dfs(int cur, int used, int max) {
        if (max >= ans) return;
        if (cur == n) {
            ans = max;
            return;
        }
        // 优先分配给空闲工人
        if (used < k) {
            sum[used] = jobs[cur];
            dfs(cur + 1, used + 1, Math.max(max, sum[used]));
            sum[used] = 0;
        }
        for (int i = 0; i < used; ++i) {
            sum[i] += jobs[cur];
            dfs(cur + 1, used, Math.max(max, sum[i]));
            sum[i] -= jobs[cur];
        }
    }
}
  • 时间复杂度：$O(k^n)$
  • 空间复杂度：$O(k)$