Shortest Job First

一个处理器要处理一堆request，一次只能处理一条，如果它有几个积压着的requests，它会先执行持续时间短的那个；对于持续时间相等的requests，先执行最早到达处理器的request。问平均每个request要等多久才能被处理。

• input：
  requestTimes，每个request到达处理器的时间;
  durations, 每个request要处理的持续时间。
  两个数组是一一对应的，并已按requestTimes[]从小到大排序过。

• example 1
  requestTime: [0, 2, 4, 5]
duration: [7, 4, 1, 4]
  题目要求是shortest task first。先处理p1，处理之后t=7；之后处理p3（当前可处理任务重用时最短的）。之后依次是p2和p4。average waiting time是(0+3+6+7)/4 = 4。

• example 2
  requestTime: [0, 1, 3, 9]
duration: [2, 1, 7, 5] 题目要求是shortest task first。先处理p1，处理之后t=2；之后依次是p2,p3, p4。average waiting time是(0+1+0+1)/4 = 0.5。

Solution

class Solution {
  public:
    double ShortJobFirst(vector<int>& requestTime, vector<int>& duration) {
      int n = requestTime.size();
      double res = 0;
      if ( n <= 1 ) return res;
      priority_queue<pair<int, int> > jobs;
      int t = duration[0];
      int i = 1, count = 1;
      for ( int count = 1; count != n; count++ ) {
        while ( i < n and requestTime[i] <= t ) {
          jobs.push(pair<int, int>(-duration[i], i));
          i++;
        }
        if ( jobs.empty() ) t += duration[i++];
        else {
          int dt = -jobs.top().first, j = jobs.top().second;
          jobs.pop();
          res += t - requestTime[j];
          t += dt;
        }
      }
      return res/n;
    }
};

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