流水线调度问题【java版本】

题目要求
N个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为a[i]和b[i]。你可以安排每个作业的执行顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。求这个最少的时间。

思路：
需要M2尽可能早用多用不出现空闲的状态。
将任务分成两类
第一类为a[i]<b[i]，该种任务需要保证M2尽早开始，故非降序排列
第二类为a[i]>=b[i],这种任务会在M1中阻塞较久时间，所以需要M2中更忙一点也就是更晚结束，故非升序排列。
因为要保证第二台机器尽早开始故将第二类任务加在第一类之后。

实现：

import java.util.Arrays;

public class Johnson {
    public static void main(String[] args) {
        int[] a = {3, 4, 8, 10};
        int[] b = {6, 2, 9, 15};
        int sum = flowShop(a, b);
        System.out.println(sum);
    }

    public static int flowShop(int[] a, int[] b) {
        int[] order = new int[a.length];
        Work[] works = new Work[a.length];
        for (int i = 0; i < a.length; i++) {
            int key = a[i] > b[i] ? b[i] : a[i];
            boolean job = a[i] <= b[i];
            works[i] = new Work(key, i, job);
        }
        Arrays.sort(works);
        int j = 0;
        int k = a.length - 1;
        for (int i = 0; i < a.length; i++) {
            if (works[i].job) order[j++] = works[i].index;
            else order[k--] = works[i].index;
        }
        //将第一类任务按照升序排列，第二类任务按降序排列
        // 后者接在前者之后
        j = a[order[0]];
        k = j + b[order[0]];
        for (int i = 1; i < a.length; i++) {//到第 i 个任务的时候是第一台机器先干完还是第二台先干完
            j += a[order[i]];
            k = j < k ? k + b[order[i]] : j + b[order[i]];
        }
        return k;
    }
}

class Work implements Comparable<Work> {
    int key;int index;boolean job;

    public Work(int key, int index, boolean job) {
        this.key = key;
        this.index = index;
        this.job = job;
    }

    @Override
    public int compareTo(Work o) {
        return key - o.key;
    }
}