Round Robin

一个处理器要处理一堆request，一次只能处理一条，每次执行一个任务最多执行时间q，接着执行等待着的下一个任务。若前一个任务没执行完则放到队尾，等待下一次执行。假设只要有任务开始以后cpu是不会空闲的，也就是说cpu开始后如果空闲了就说明没有任务了，另外Robin Round最后返回值是float。

OA 示例：
input: [0，1，4], [5, 2, 3], q = 3
output: average wait time 2.3333333

1. p1入队，
2. 执行p1 3秒，出队，t = 3;
3. p2入队，p1（剩余duration2秒，新的requestTime为3）入队；
4. 执行p2（等待时间2秒） 2秒，出队，t = 5;
5. p3入队。
6. 执行p1（等待时间2秒） 2秒，出队，t = 7;
7. 执行p3（等待时间3秒） 3秒，出队。

注意动态更新requestTime和duration的trick。

Solution

class Solution {
  public:
    double RoundRobin(vector<int>& requestTime, vector<int>& duration, int q) {
      int n = requestTime.size();
      double res = 0;
      if ( n <= 1 ) return res;
      deque<int> jobs;
      vector<int> twait(n, 0);
      int t = 0, i = 0;
      while ( i != n or ! jobs.empty() ) {
        if ( jobs.empty() ) {
          jobs.push_back(i);
          t = requestTime[i];
          i++;
        }
        int j = jobs.front();
        jobs.pop_front();
        twait[j] += t - requestTime[j];
        t += min(q, duration[j]);
        while ( i < n and requestTime[i] <= t ) jobs.push_back(i++);
        if ( duration[j] > q ) {
          duration[j] -= q;
          jobs.push_back(j);
          requestTime[j] = t;
        }
        else duration[j] = 0;
      }
      for ( int i = 0; i < n; i++ ) res += twait[i];
      return res/n;
    }
};

int main() {
  Solution sol;
  int x[3] = {0, 1, 4};
  int y[3] = {5, 2, 3};
  int q = 3;
  vector<int> requestTime(x, x + sizeof(x)/sizeof(x[0]));
  vector<int> duration(y, y + sizeof(y)/sizeof(y[0]));
  cout << sol.RoundRobin(requestTime, duration, q) << endl;
  return 0;
}