LeetCode1235：规划兼职工作

题目描述：https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/

我的踩坑经历

• 每个工作带有三个属性：startTime, endTime, profile.
• 看到这个题目，第一反应就是需要按照endTime对工作进行排序，并且这是一道动态规划的题目。
• 这里简单记录下我写出的坑：
  1、我创建了一个类Job，为了方便endTime排序，只重写Arrays.sort()方法，这次提交显示内存溢出，我猜测重新创建对象导致大量内存的消耗；
  2、动态规划定义的状态表示过于冗余
  f[i][j]: 前 i 个工作在时间 j 之前能获得的最大报酬；
• 状态转移方程：
  这里两点，如果 j 大于第 i 个作业的 endTime，那么
  f[i][j] = Math.max( f[i-1][j], f[i-1][startTime[i]]+profile[i]);
  如果 j 不大于第 i 个作业的endTime， 那么
  f[i][j] = f[i-1][j];
  这个n*m的二位数组也是造成内存溢出的元凶，于是我将状态表示压缩为一维数组，并且将Job类去掉，自己手写快排。然后显示time limited。

正确的解题思路

最后问题还是出在动态规划，重写定义动态规划的状态表示：
f[i]：前i个工作能获得的最大的报酬；
另开一个w[i] 数组记录，某个工作 j 的结束时间距离第i的工作的开始时间最近，返回工作索引 j， 不存在就返回-1。

• 状态转移方程：

if(w[i] == -1){ f[i] = Math.max(f[i-1], profile[i]);}
else f[i] = Math.max(f[i-1], f[w[i]]+profile[i]);

详细代码：

class Solution {
     private static void quickSort(int[] arry, int []arry1, int [] arry2, int l, int r) {
        if(r<=l) return;
        int x = arry[(l+r)/2];
        int i = l-1;
        int j = r+1;
        while(i<j){
            do i++; while(arry[i]<x);
            do j--; while(arry[j]>x);
            if(i<j){
                int tmp = arry[i];
                arry[i] = arry[j];
                arry[j] = tmp;

                tmp = arry1[i];
                arry1[i] = arry1[j];
                arry1[j] = tmp;

                tmp = arry2[i];
                arry2[i] = arry2[j];
                arry2[j] = tmp;
            }
        }
        quickSort(arry,arry1,arry2, l,j);
        quickSort(arry,arry1, arry2,j+1,r);
    }
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        if(n== 0) return 0;
        if(n== 1) return profit[0];
        quickSort(endTime, startTime, profit, 0,n-1);

        int[] w = new int[n];
        int[] results = new int[n];
        for(int i = 1;i<n;i++){
            //找第i个作业的开始时间距离最近的某个作业的结束时间，返回这个作业的结束时间
            int j = i-1;
            while(j>=0 && endTime[j]>startTime[i]){
                j--;
            }
            w[i] = j;
        }
        results[0] = profit[0];
        int max = results[0];
        for(int i = 1;i<n;i++){
            if(w[i] == -1){
                results[i] = Math.max(results[i-1], profit[i]);
            }
            else{
                results[i] = Math.max(results[i-1], results[w[i]]+profit[i]);
            }

        }
        return results[n-1];
    }
}