Java加权作业调度随机生成作业 求解最大利润时栈溢出

栈溢出是递归进入无限循环导致的，由两个逻辑bug共同触发：

• 作业生成规则不合法：当前代码随机生成作业时，开始时间取0-29的随机值，结束时间取0-49的随机值，没有约束开始时间 < 结束时间，会生成大量时间逻辑无效的作业。
• 非冲突作业查找逻辑索引错误：latestNonConflict方法的循环从j = i - 1位置开始查找，第一个遍历到的就是当前正在判断的作业本身。如果遇到无效作业（开始时间≥结束时间），就会误判当前作业和自身不冲突，返回索引i-1。后续递归调用findMaxProfitRec(arr, i+1)时传入的长度参数和当前调用完全一致，递归永远无法触达终止条件，最终耗尽栈空间抛出异常。

就算所有作业都合法，从j = i -1开始遍历也是多余的——合法作业的结束时间必然大于自身开始时间，永远不可能满足不冲突条件。

按顺序修改两处代码即可：

1. 调整作业生成逻辑，强制保证结束时间晚于开始时间，替换main方法中的循环代码：

Random rand = new Random();
for (int i = 0; i<arr.length; i++) {
    int start = rand.nextInt(30);
    // 结束时间最小为start+1，最大为start+30，和原逻辑的数值范围保持一致
    int finish = start + 1 + rand.nextInt(30);
    int profit = rand.nextInt(300);
    arr[i] = new Job(start, finish, profit);
}

2. 修正latestNonConflict的循环起始位置，跳过当前作业本身，从它的前一个作业开始向前查找：

static int latestNonConflict(Job arr[], int i)
{
    for (int j = i - 2; j >= 0; j--)
    {
        if (arr[j].finish <= arr[i - 1].start)
            return j;
    }
    return -1;
}

当前纯递归实现的时间复杂度是O(2^n)，仅适合作业数小于20的小规模场景。如果需要处理更多作业，建议改成记忆化递归或动态规划实现，搭配二分查找优化非冲突作业的查找过程，时间复杂度可以降到O(nlogn)，同时也能避免递归层级过深导致的栈溢出问题。

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