C#实现Weighted Job Scheduler获取关联JobID索引报错求助

错误原因 #

• 数组类型选择错误：你声明的int[,]是二维固定数组，必须同时传入行、列两个索引才能访问元素，单独写jobsId[i]不符合语法要求，且你初始化时仅分配了1行1列的存储空间，后续i≥1时访问jobsId[i,0]会直接触发数组越界。
• 列表追加逻辑错误：固定长度的二维数组不支持动态追加元素，且LINQ的Append()方法会返回新的数组，你没有将结果赋值给变量，操作不会生效。
• 利润计算逻辑错误：profitSum没有在每次i循环开始时重置为当前任务的利润，会重复累加历史值导致计算结果错误。
• 状态同步缺失：当当前任务组合利润不大于前序最优利润时，没有给dp[i]和jobsId[i]赋值，会导致状态断层。

修正后完整代码 #

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        var jobs = startTime
            .Select((_, i) => new
            {
                id = i,
                s = startTime[i],
                e = endTime[i],
                p = profit[i],
            }
            )
            .OrderBy(x => x.e)
            .ToArray();

        int n = jobs.Length;
        int[] dp = new int[n];
        // 用List<int>数组存储每个dp状态对应的任务ID列表
        List<int>[] jobsId = new List<int>[n];
        
        dp[0] = jobs[0].p;
        jobsId[0] = new List<int> { jobs[0].id };

        for (var i = 1; i < n; i++) {
            int profitSum = jobs[i].p;
            int task = -1;
            // 找最近的不冲突任务
            for (var j = i-1; j >= 0; j--) {
                if (jobs[j].e <= jobs[i].s) {
                    task = j;
                    break;
                }
            }

            if (task != -1) {
                profitSum += dp[task];
            }

            if (profitSum > dp[i-1]) {
                dp[i] = profitSum;
                // 复制前序不冲突任务的ID列表
                jobsId[i] = task == -1 ? new List<int>() : new List<int>(jobsId[task]);
                // 加入当前任务ID
                jobsId[i].Add(jobs[i].id);
            } else {
                // 沿用前序最优解
                dp[i] = dp[i-1];
                jobsId[i] = new List<int>(jobsId[i-1]);
            }
        }
        
        // 输出最大利润对应的任务ID
        Console.WriteLine("最大利润关联的JobID：" + string.Join(",", jobsId[n-1]));
        return dp[n-1];
    }

    public static void Main(string[] args)
    {
        int[] startTime = { 1,3,6,2 };
        int[] endTime = { 2,5,7,8 };
        int[] profit = { 50,20,100,200 };

        Program job = new Program();
        Console.WriteLine("最大利润：" + job.JobScheduling(startTime, endTime, profit));
    }
}

运行结果 #

最大利润关联的JobID：3
最大利润：200

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