Round Robin

话说有一堆进程，有到达时间arriveTime[]，还有执行时间executeTime[]。
我们这里有一个q，就是最大执行时间片。
需要我们模拟一下Round Robin这种调度方法。
例子： 【0，1，4】 【5，2，3】 q=3. 输出的是average wait time 2.3333333
例子的解释又臭又长。

import java.util.LinkedList;
import java.util.Queue;

class Process {
    int arrTime;
    int exeTime;

    Process(int arr, int exe) {
        arrTime = arr;
        exeTime = exe;
    }
}

public class RoundRobin {

    public static void main(String[] args) {
        int[] Atime = {0,1,4};
        int[] Etime = {5,2,3};
        System.out.println(Solution(Atime, Etime, 3));
    }

    // arrive time array: Atime
    // execute time array: Etime
    public static float Solution(int[] Atime, int[] Etime, int q) {
        // Corner case
        if (Atime == null || Etime == null || Atime.length != Etime.length) {
            return 0;
        }
        int length = Atime.length;

        // build a queue of process
        Queue<Process> queue = new LinkedList<Process>();

        int curTime = 0, totalWaitTime = 0, index = 0;

        // 当队列不为空或者没有处理完的时候
        while (!queue.isEmpty() || index < length) {
            if (queue.isEmpty()) {
                queue.offer(new Process(Atime[index], Etime[index]));
                curTime = Atime[index++];
            } else {
                // 处理当前的进程
                Process cur = queue.poll();
                totalWaitTime += curTime - cur.arrTime;
                curTime += Math.min(q, cur.exeTime);

                // 把那些在处理时来排队的人加入到队列中
                while (index < length && Atime[index] <= curTime) {
                    queue.offer(new Process(Atime[index], Etime[index]));
                    index++;
                }

                // 如果我们当前的进程没有处理完，就需要继续加入到尾部
                if (cur.exeTime > q) {
                    queue.offer(new Process(curTime, cur.exeTime - q));
                }
            }
        }

        return (float) totalWaitTime / length;
    }
}