Shortest Job First

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

Screen Shot 2017-09-13 at 17.09.28.png

import java.util.*;
public class Solution {
    static class Process
    {
        int arrTime;
        int exeTime;
        public Process(int arrTime, int exeTime)
        {
            this.arrTime = arrTime;
            this.exeTime = exeTime;
        }
    }
    public static double SJL(int[] req, int[] dur)
    {
        if(req == null || req.length == 0) return 0;
        PriorityQueue<Process> queue = new PriorityQueue<>(new Comparator<Process>()
        {
            @Override
            public int compare(Process a, Process b)
            {
                if(a.exeTime == b.exeTime) return a.arrTime - b.arrTime;
                else return a.exeTime - b.exeTime;
            }
        });
        int t = 0, sum = 0, i = 0;
        while(i < req.length || !queue.isEmpty())
        {
            if(queue.isEmpty())
            {
                queue.offer(new Process(req[i], dur[i]));
                t = req[i];
                i++;
            }
            else
            {
                Process p = queue.poll();
                sum += (t - p.arrTime);
                t += p.exeTime;
                while(i < req.length && req[i] <= t)
                {
                    queue.offer(new Process(req[i], dur[i]));
                    i++;
                }
            }
        }
        return (sum + 0.0) / req.length;
    }
    public static void main(String[] args)
    {
        int[] req = {1, 3, 3, 6, 6, 6, 7};
        int[] dur = {2 ,2 ,3 ,2, 4, 4, 2};
        System.out.println(SJL(req, dur));
    }
}