工作调度问题

/**
 * 工作调度问题
 * 有N项工作，每项工作分别在Si时间开始，在Ti时间结束。对于每项工作。你都可以选择参与与否
 * 如果先择了参与那么自始自终都必须全程参与。此外，参与工作的时间段不能重叠
 * (即使是开始的瞬间和结束的瞬间的重叠也是不允许的)你的目标是尽可能多的工作，
 * 那么最多能参与多少项工作呢？
 * @author haofan.whf
 * @version $Id: JobScheduler.java, v 0.1 2018年06月12日 下午5:58 haofan.whf Exp $
 */
public class JobScheduler {

    public void schedule(int N, int[] S, int[] T){
        /**
         * 思路，贪婪算法
         * 我们可以选择3中规则
         * 1.始终选择开始时间最早的工作
         * 2.始终选择耗时最短的工作
         * 3.始终选择结束时间最早的工作
         *
         * 对于规则1我们可以想到一个反例
         * 比如S={1,3,5} T={10,4,6}，那么套用规则1我们将只会参与1-10
         * 但是最优解是3-4,5-6
         * 对于规则2我们也可以想到一个反例
         * 比如S={1,3,5} T={4,5,8}，那么套用规则2我们将只会参与3-5
         * 但是最优解是1-4,5-8
         *
         * 正确的规则只有3
         */
        Arrays.sort(T);
        int jobCnt = 0;
        int previousEnd = 0;
        for (int i = 0; i < N; i++) {
            if(previousEnd < S[i]){
                jobCnt ++;
                previousEnd = T[i];
                System.out.println("start:" + S[i] + ",end:" + T[i]);
            }
        }
        System.out.println("jobCnt:" + jobCnt);
    }

}