Job Schedule

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum

Naive Thinking:  怎么看怎么像DP，还是经典的那种。
基本逻辑为：
opt[i] // maximum within time [0,i] without overlapping jobs
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[t] + cost of job[k] | where 0<=t<i , job[k]has start time >t, end time<=i)

但是实际做才发现，每次更新opt[i]都要遍历一遍所有job，这很不好，因为即使将job排序也不能有效减少算法复杂度O(n^3)，所以想到了这题跟 maximum non-overlapping intervals 很像。可能可以用Greedy。用Greedy先写一个例子

[  1  ]  [   3     ]
    [    5    ]

如果greedy是优先选start time 小的，这个例子就会通不过。

如果是优先选cost高的，以下这个例子又会不通过。

[  3  ]  [   3     ]
    [    5    ]


那么看来greedy是不可行的，还是老老实写DP。但还是有必要重新讨论一下如何减少一个Loop的。

可不可以先把用什么方法把任意[i,j]时间段对应的job先求出来，如果能在O(n^2)时间内求出来就算是成功的。可以，先将job按start time->end time排序，然后用一个二维数组或者map存每一个时间段对应的job编号，需要用O(n^2)的space。


import java.util.Arrays;
import java.util.Comparator;

class Job{
        int start,end,cost;
        Job(int s, int e, int c){
            start = s;
            end = e;
            cost = c;
        }
    }
public class Solution{

    public static void main(String args[]){
        int n = 1;
        Job[] jobs = new Job[n];
        jobs[0] = new Job(0,3,1);
        jobs[1] = new Job(3,6,3);
        jobs[2] = new Job(1,5,5);
        jobs[3] = new Job(6,7,1);
        jobs[4] = new Job(7,10,4);
        jobs[5] = new Job(6,8,2);
        jobs[6] = new Job(8,10,2);
        jobs[7] = new Job(1,4,6);
        jobs[8] = new Job(3,7,6);
        jobs[9] = new Job(3,8,8);
        Solution s = new Solution();
        System.out.println(s.maxCostOfJobs(jobs));
    }

    public int maxCostOfJobs(Job[] jobs){
        // edge case
        if(jobs.length==0){return 0;}

        // sort the jobs by start time ->end time
        Comparator<Job> comparator = new Comparator<Job>(){
            @Override
            public int compare(Job a, Job b){
                if(a.start > b.start)
                    return 1;
                else if(a.start < b.start)
                    return -1;
                else{
                    if(a.end > b.end)
                        return 1;
                    else if(a.end < b.end)
                        return -1;
                    else
                        return 0;
                }
            }
        };
        Arrays.sort(jobs,comparator);

        // match time interval to job cost
        int min = jobs[0].start, max = jobs[jobs.length-1].end;
        int[][] match = new int[max-min+1][max-min+1];
        Job pre = jobs[0];
        for(int i = 0;i < jobs.length;i++){
            if(jobs[i].start==pre.start && pre.cost > jobs[i].cost){
                match[jobs[i].start-min][jobs[i].end-min] = pre.cost;
            }else{
                match[jobs[i].start-min][jobs[i].end-min] = jobs[i].cost;
                pre = jobs[i];
            }
        }

        // DP to get maximum cost
        int opt[] = new int[max-min+1];
        for(int i = 1;i < opt.length;i++){
            opt[i] = opt[i-1];
            for(int t = 0;t < i;t++)
                opt[i] = Math.max(opt[i], opt[t] + match[t][i]);
        }

        return opt[opt.length-1];

    }
}