加权项目时间计划问题

/**
 * @author Zhai
 * 2020/8/15 15:49
 */

public class Test {
    public static void main(String[] args) {
        int[][] input = new int[8][3];
        input[0] = new int[]{1, 4, 5};
        input[1] = new int[]{3, 5, 1};
        input[2] = new int[]{0, 6, 8};
        input[3] = new int[]{4, 7, 4};
        input[4] = new int[]{3, 8, 6};
        input[5] = new int[]{5, 9, 3};
        input[6] = new int[]{6, 10, 2};
        input[7] = new int[]{8, 11, 4};
        System.out.println(dynamic(input));
    }

    public static int dynamic(int[][] input) {
        // 优化
        if (input.length == 0) {
            return 0;
        }
        if (input.length == 1) {
            return input[0][2];
        }
        // 每个任务如果做之后, 那么前一个可做的任务
        int[] pre = new int[input.length];
        for (int z = input.length - 1;z >= 0;z--) {
            if (z == 0) {
                pre[z] = -1;
            }
            // b为前一个可做任务的index
            for (int b = z - 1;b >= 0;b--) {
                if (input[b][1] <= input[z][0]) {
                    pre[z] = b;
                    break;
                } else if (b == 0) {
                    // 如果b为0,且不满足上面判断条件,则前面没有任务
                    pre[z] = -1;
                }
            }
        }
        int[] dp = new int[input.length];
        // 初始化边界
        dp[0] = input[0][2];
        for (int i = 1;i < input.length; i++) {
            if (pre[i] == -1) {
                dp[i] = Math.max(input[i][2], dp[i - 1]);
            } else {
                dp[i] = Math.max(dp[pre[i]] + input[i][2], dp[i - 1]);
            }
        }
        return dp[input.length - 1];
    }
}