ディスクコントローラ

問題の説明

HDDは一度に1台しか処理できません.ディスクコントローラを実装する方法はいくつかあります.最も一般的な方法は、リクエストの受信順序に従って処理することである.

例:

0ミリ秒時3ミリ秒のA要求

Bジョブ要求

ミリ秒(

ミリ秒)

msの時点で6ミリ秒のCタスクを要求
受け取った要求は同じです.下図のように.

一度に1つのリクエストしか実行できないため、各タスクをリクエストの順序で処理する場合:

A:3ミリ秒(リクエストから終了まで:3ミリ秒)

B:1 ms待機開始、3 ms動作開始、12 ms完了(リクエストから終了:11 ms)

C:2ミリ秒～2ミリ秒、12ミリ秒～18ミリ秒(リクエストから終了まで:16ミリ秒)
各タスクの要求から終了までの平均時間は10ミリ秒(=(3+11+16)/3)である.

でもA→C→B順に処理すると

A:3ミリ秒(リクエストから終了まで:3ミリ秒)

C:2ミリ秒～2ミリ秒、3ミリ秒～9ミリ秒、7ミリ秒～

B:1 msで始まり、9 msで始まり、18 msで終了(リクエストから終了まで:17ミリ秒)
A→C→Bの順に処理すると,各タスクの要求から終了までの平均時間は9 ms(=(3+7+17)/3)となる.

各タスクについて、「要求タスクの時点、タスク所要時間」を含む2 Dタイルジョブをパラメータとして指定した場合は、要求から終了までのタスクの平均値を最小限に抑えるためのソルバを作成します.(ただし小数点以下)

せいげんじょうけん

jobsの長さは1または500以下です.
ジョブの各行は、タスクの[タスクを要求する時間、タスクに要する時間]です.
各タスクについて、タスクを要求する時間は1000を超えません.
各タスクに要する時間は1000時間を超えない.
ハードディスク(HDD)が動作していない場合は、リクエストのタスクを先に処理します.
I/O例
jobs return
[[0, 3], [1, 9], [2, 6]] 9

I/O例説明

問題の例は以下の通りです.
タスクリクエストは、0ミリ秒の時点で3ミリ秒受信されます.
1ミリ秒の時点で9ミリ秒のタスクリクエストを受信します.
2ミリ秒の時点で6ミリ秒のタスクリクエストを受信します.

import java.util.*;

class Solution {
public static int solution(int[][] jobs) {

      Arrays.sort(jobs, new Comparator<int[]>() {
          public int compare(int[] o1, int[] o2) {
              if(o1[0] <= o2[0]){
                  return -1;
              }
              return 1;
          }
      });      

      PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
          public int compare(int[] o1, int[] o2) {
              if(o1[1] < o2[1]){
                  return -1;
              }
              return 1;
          }
      });

      int time = 0;
      int index = 0;
      float answer = 0;

      while(true){
          while(index < jobs.length && jobs[index][0] <= time){
              queue.offer(jobs[index]);
              index ++;
          }
          if(queue.size() == 0){
              time = jobs[index][0];
              continue;
          }
          int[] job = queue.poll();
          time += job[1];
          answer += time - job[0];
          if(index == jobs.length && queue.size() == 0){
              break;
          }
      }

      answer /= jobs.length;
      return (int)answer;
    }
}