1、前言

题目描述

2、思路

本题的思路其实用的贪心 + dp，贪心体现在：先将工作根据结束时间从小到大排序，这样是有利于后续的 dp。
dp 的思路是：首先定义一个 dp 数组，dp[i] 代表到了第 i 份工作时的最大利润。如果选择第 i 份工作，那么要向前找到一个跟 i 时间不重合的利润 dp[j]，即 dp[j] + profit[i]；如果不选第 i 份工作，那么直接继承 dp[i - 1]。

偷来的思路图

3、代码

class Solution {
    class Job{
        int startTime, endTime,  profit;

        public Job(int startTime, int endTime, int profit) {
            this.startTime = startTime;
            this.endTime = endTime;
            this.profit = profit;
        }
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        List<Job> list = new ArrayList<>();
        for (int i = 0; i < n; i++)
           list.add(new Job(startTime[i], endTime[i], profit[i]));
        list.sort((o1, o2) -> o1.endTime - o2.endTime);
        int dp[] = new int[n + 1];
        dp[0] = 0; // 初始第一个虚拟的dp，报酬为0
        for (int i = 1; i <= n; i++) {
            int pre = 0;
            for (int j = i - 1; j >= 0; j--) {
                // 向前寻找“最近的”“已完成的"兼职工作
                if (list.get(j).endTime <= list.get(i-1).startTime) {
                    pre = j + 1; break;
                }
            }
            dp[i] = Math.max(dp[i - 1], dp[pre] + list.get(i-1).profit);
        }
        return dp[n];
    }
}