[leetCode]1235. 规划兼职工作

动态规化

class Solution {

    class job {
        int start, end, profit;
        job (int s, int e, int p) {
            start = s;
            end = e;
            profit = p;
        }
    }


    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[] dp = new int[n+1];
        job[] jobs = new job[n];
        for (int i = 0; i < n; i++)
            jobs[i] = new job(startTime[i], endTime[i], profit[i]);
        Arrays.sort(jobs, Comparator.comparingInt(o->o.end));
        // d[i] 表示包括第i份工作之前所有工作能取得的最大利益
        // 初始化只做当前工作的利益
        for(int i=0;i<n;i++)
            dp[i]=jobs[i].profit;
        for (int i = 1; i < n; i++) {
            // 工作重叠则做最赚钱的那一份工作
            dp[i] = Math.max(dp[i-1], jobs[i].profit);
            for (int j = i - 1; j >= 0; j--) {
                if (jobs[j].end <= jobs[i].start) {
                    // 如果第i份工作之前有不重叠的工作
                    dp[i] = Math.max(dp[i], dp[j] + jobs[i].profit);
                    // 找到第一个不重叠的位置退出这样dp[j]最大
                    break;
                }
            }
        }
        return dp[n-1];    
    }
}

参考

动态规化 C++
动态规化 java