大厂算法：项目排期

一、题目 §

项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。

二、输入 §

第一行输入为M个需求的工作量，单位为天，用逗号隔开。

例如：X1 X2 X3 … Xm 。表示共有M个需求，每个需求的工作量分别为X1天，X2天…Xm天。 其中0<M<30；0<Xm<200

第二行输入为项目组人员数量N

三、输出 §

最快完成所有工作的天数

四、示例 §

输入：
6 2 7 7 9 3 2 1 3 11 4
2

输出：
28

说明：共有两位员工，其中一位分配需求 6 2 7 7 3 2 1共需要28天完成，另一位分配需求 9 3 11 4 共需要27天完成，故完成所有工作至少需要28天。

五、题解 §

1. 问题解有单调性，在一个区间范围内。考虑二分法找可行解和最优解
2. 验证解的正确性时尝试过贪心和动态规划，都没有得到最优解。暴搜 DFS可以找到最优解，但是明显效率不高

5.1 Java 实现 §

package org.stone.study.algo.ex202412;
import java.util.Arrays;
import java.util.Scanner;
public class ProjectScheduler {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] workLoads = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = Integer.parseInt(sc.nextLine());

        int ans = new ProjectScheduler().minCompletionTimeByDFS(workLoads, n);
//        int ans = new ProjectScheduler().minCompletionTimeByDP(workLoads, n);
        System.out.println(ans);
    }

    /**
     * 二分查找最小的工期
     * @param workLoads 每个任务的工作量
     * @param n 工人数量
     * @return
     */
    public int  minCompletionTimeByDFS(int[] workLoads, int n) {
        // 最长的工作量给一个人做，作为项目整体工期的最小值
        int left = Arrays.stream(workLoads).max().orElse(0);
        // 工作量总和给一个人做，作为项目整体工期的最大值
        int right = Arrays.stream(workLoads).sum();
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(check(workLoads, mid, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    /**
     * 检查是否可以完成任务
     * @param workLoads 每个任务的工作量
     * @param limit 每个人最大的工作量，超过这个值，就需要另一个工人
     * @param n 工人数量
     * @return
     */
    public boolean check(int[] workLoads, int limit, int n) {
        int[] allocates = new int[n];
        // 贪心算法没能解决所有 case，需要回溯算法遍历所有可能
        return dfs(workLoads, 0, limit, allocates);
    }

    /**
     * 深度优先搜索
     * @param workLoads 每个任务的工作量
     * @param i 当前任务的索引
     * @param limit 每个人最大的工作量
     * @param allocates 每个人已经分配的工作量
     * @return
     */
    private boolean dfs(int[] workLoads, int i, int limit, int[] allocates) {
        if(i == workLoads.length) {
            return true;
        }
        // 当前任务
        int curWorkLoad = workLoads[i];
        // 遍历每个人，找到一个合适的工人
        for(int j = 0; j < allocates.length; j++) {
            if (allocates[j] + curWorkLoad <= limit) {
                allocates[j] += curWorkLoad;
                if (dfs(workLoads, i + 1, limit, allocates)) {
                    return true;
                }
                allocates[j] -= curWorkLoad;
            }
        }

        return false;
    }

    /**
     * 动态规划解法,得不到最优解。这玩意儿是玄学，不确定原因
     * @param tasks
     * @param n
     * @return
     */
    public int minCompletionTimeByDP(int[] tasks, int n) {
        int m = tasks.length;
        int[] prefixSum = new int[m + 1];

        // 计算前缀和，prefixSum[i] 表示前 i 个任务的总工作量
        for (int i = 0; i < m; i++) {
            prefixSum[i + 1] = prefixSum[i] + tasks[i];
        }

        // dp[i][j] 表示前 i 个任务分配给 j 个开发人员的最小化最大工作量
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // 初始条件：一个开发人员负责所有任务
        for (int i = 0; i <= m; i++) {
            dp[i][1] = prefixSum[i];  // 所有任务由一个开发者完成
        }

        // 填充 DP 表
        for (int j = 2; j <= n; j++) {  // j 个开发人员
            for (int i = 1; i <= m; i++) {  // i 个任务
                for (int k = 0; k < i; k++) {  // 划分点
                    int currentMaxWorkload = Math.max(dp[k][j - 1], prefixSum[i] - prefixSum[k]);
                    dp[i][j] = Math.min(dp[i][j], currentMaxWorkload);
                }
            }
        }

        return dp[m][n];
    }
}

5.2 Python实现 §

# 二分找最小工期
def min_time_to_complete(tasks, n):
    left, right = max(tasks), sum(tasks)
    while left < right:
        mid = (left + right) // 2
        if check(tasks, n, mid):
            right = mid
        else:
            left = mid + 1
    return left

# DFS 暴搜所有的分配方案，看是否存在一种分配方案，使得所有任务在 limit 时间内完成
def check(tasks, n, limit):
    allocated = [0] * (n)
    return dfs(tasks, 0, limit, allocated)

# 对任务 i，尝试分配给每一个工人 j
def dfs(tasks, i, limit, allocated):
    if i == len(tasks):
        return True
    
    cur_workload = tasks[i]
    for j in range(n):
        if allocated[j] + cur_workload <= limit:
            allocated[j] += cur_workload
            if dfs(tasks, i + 1, limit, allocated):
                return True
            allocated[j] -= cur_workload
    return False

if __name__ == '__main__':
    tasks = list(map(int, input().split()))
    n = int(input())

    print(min_time_to_complete(tasks, n))