Shortest Job First

一个处理器要处理一堆request，一次只能处理一条，如果它有几个积压着的requests，它会先执行持续时间短的那个；对于持续时间相等的requests，先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input：requestTimes[]，每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的，并已按requestTimes[] 从小到大排序过

public double CalWaitingTime(int requestTimes[], int[] durations[]){}

用priorityqueue做，地里有一个两层循环的答案，没仔细看，做完round robin以后发现思路很相似。注意用priorityqueue写comparator的时候，要先判断两者的execute time,如果execute time相同，则返回arrival time之差，即先按执行时间排序，若执行时间相同则按到达的时间排。

文／白马书院的姑娘（简书作者）
原文链接：http://www.jianshu.com/p/bb522c1157b0
著作权归作者所有，转载请联系作者获得授权，并标注“简书作者”。

import java.util.Comparator;
import java.util.PriorityQueue;

public class ShortestJobFirst {

    // 最短任务先执行
    // 如果任务长短相同，先到达，先执行
    public static void main(String[] args) {
        int[] req = {1,2,4,6,7,12,15};
        int[] dur = {3,3,3,5,8,10,10};

        System.out.println(waitTimeAvg(req, dur));
    }

    public static float waitTimeAvg(int[] req, int [] dur) {
        // corner case
        if (req == null || req.length == 0 || dur == null || dur.length == 0 || req.length != dur.length) {
            return 0;
        }

        int curTime = 0, waitTime = 0, index = 0;
        int len = req.length;

        PriorityQueue<Process> pq = new PriorityQueue<>(new Comparator<Process> () {
            public int compare(Process a, Process b) {
                // idea: first try to order by execution time,
                //       if execution time is equal, then order by request time
                if (a.exeTime == b.exeTime) {
                    return a.arrTime - b.arrTime;
                }
                return a.exeTime - b.exeTime;
            }
        });

        while (!pq.isEmpty() || index < len) {
            if (pq.isEmpty()) {
                pq.offer(new Process(req[index], dur[index]));
                curTime = req[index++];

            } else {
                // execute current process
                Process curProcess = pq.poll();
                waitTime += curTime - curProcess.arrTime;
                curTime += curProcess.exeTime;

                // add waiting process to list
                while (index < len && req[index] < curTime) {
                    pq.add(new Process(req[index], dur[index]));
                    index++;
                }
            }
        }


        return (float) waitTime / len;
    }
}