题目描述

原题链接： LeetCode.1235 规划兼职工作

解题思路

• 想到了按照结束时间排序后用动态规划来处理， 但是又局限在了以结束时间为维度进行递推， 又卡在了时间不连续无法高效计算到最晚结束时间范围内所有时间对应值这一问题上， 看了题解才知道用排序后的兼职工作数量为维度去递推：
  • 递推数组定义为前i个结束的兼职工作能得到的最大报酬；
  • 递推公式是 dp[i] = Math.max(dp[i - 1], dp[k] + profit[i]), 其中k是结束时间不晚于startTime[i]的最晚结束工作， 可以通过二分法在[0, i-1]范围内确认k的值；
  • dp[n]就是最终所求答案， 时间复杂度是排序所需的O(n\(log_2 n\)) + 动态规划所需的O(n\(log_2 n\))， 空间复杂度是辅助关联排序后三个输入数组的变量所需的O(n)；
• 本题是很有实际应用意义的动态规划题， 而且也用到二分法巧妙加速递推过程， 值得记录用以回顾；
• 动态规划的思路最难的还是确认定义， 确认解出来后再看只能怪自己最初怎么想不到， 希望后面能总结出自己能快速反应抓住的技巧/规律吧。

解题代码

• 排序+动态规划+二分：

    /**
     * 看官方题解写的代码
     * 执行用时： 27 ms , 在所有 Java 提交中击败了 73.74% 的用户
     * 内存消耗： 53.72 MB , 在所有 Java 提交中击败了 96.46% 的用户
     */
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = endTime.length;
        // 按结束时间将工作对应的下标排序
        Integer[] indexes = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(indexes, Comparator.comparingInt(i -> endTime[i]));
        // dp[i]表示从前i份工作中能获得的最大报酬
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            Integer idx = indexes[i - 1];
            // 用二分法在前i-1份工作中找到结束时间不晚于第i份工作开始时间的工作是第几份
            int left = 0, right = i - 1;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (endTime[indexes[mid]] > startTime[idx]) {
                    right = mid;
                }
                else {
                    left = mid + 1;
                }
            }
            dp[i] = Math.max(dp[i - 1], dp[left] + profit[idx]);
        }
        return dp[n];