Java作业调度问题代码纠错：贪心算法实现错误排查

核心错误分析 #

你的代码存在两个关键问题，导致贪心算法无法正确计算最优解：

• 未更新时间变量time：当选中一个作业后，代码没有对time进行递增操作。这会导致所有截止日期大于初始值0的作业都会被错误选中，完全忽略了同一时间只能执行一个作业的限制。比如多个截止日期为1的作业会被全部统计，但实际上同一时间只能完成一个。

• 调度逻辑错误：简单判断j.deadline > time的逻辑不严谨。这种方式只会按顺序占用当前时间点，无法为后续高利润作业预留合适的时间槽。比如一个截止日期为3的作业，当前time为1，直接占用时间点1会浪费时间点3，可能导致另一个截止日期为3的更高利润作业无法安排。

修正思路与代码 #

正确的贪心策略应该是：先按利润降序排序作业，然后为每个作业寻找其截止日期之前的最晚可用时间槽，确保高利润作业尽可能占用不影响其他作业的时间点。

修正后的代码如下：

int[] JobScheduling(Job arr[], int n) {
    // 按利润从高到低排序作业
    Arrays.sort(arr, (a, b) -> b.profit - a.profit);
    
    // 确定所有作业中的最大截止日期，用于创建时间槽数组
    int maxDeadline = 0;
    for (Job job : arr) {
        if (job.deadline > maxDeadline) {
            maxDeadline = job.deadline;
        }
    }
    
    // 用数组标记时间槽是否被占用，索引对应时间点（从1开始）
    boolean[] occupiedSlots = new boolean[maxDeadline + 1];
    int completedJobs = 0;
    int totalProfit = 0;
    
    for (Job job : arr) {
        // 从作业的截止日期倒序查找第一个可用时间槽
        for (int i = job.deadline; i > 0; i--) {
            if (!occupiedSlots[i]) {
                occupiedSlots[i] = true;
                completedJobs++;
                totalProfit += job.profit;
                break;
            }
        }
    }
    
    return new int[]{completedJobs, totalProfit};
}

修正点说明 #

1. 时间槽跟踪：通过occupiedSlots数组记录每个时间点的占用状态，确保同一时间只能安排一个作业。
2. 合理分配时间：对每个作业从截止日期倒序查找可用槽，既保证作业能在截止前完成，又为其他作业预留了更早的时间槽。
3. 简化排序步骤：直接使用Arrays.sort对原数组排序，省去了转ArrayList的步骤，提高效率。

内容的提问来源于stack exchange，提问作者Saikat Mandal