プログラマ-Java付きディスクコントローラ

17208 ワード
お尻 Java ディスクコントローラ 優先キュー プログラマ テキストリンク
プログラマ質問リンク
問題の説明をスキップします.

問題を解く


この問題の核心は、すべてのリクエストを処理する遅延が最も短いことです.
この重要な問題を解決する方法は次のとおりです.
どうせ作業は時間順に入るのですが、この問題で分かりやすいように2つのQueueを使います.
JobQueue リクエスト時間順にソート
  • 実際の処理のための「リードキュー」(readyQueueは常に動作時間の昇順に並べなければならない)
    • .

    なぜReadyQueueは操作時間の昇順でソートする必要があるのですか?


    readyQueueは実際にはタスクを処理するためのQueueです.
    readyQueueのタスクには、すべてのリクエスト時間が現在の時間を超えたジョブがあります.
    待機時間を短縮するには、現在処理可能なすべてのリクエストのタスクを処理する必要があります.これらのリクエストの処理時間は短いです.

    アルゴリズム#アルゴリズム#

  • は、すべての要求をjobQueueに入れ、時間順にソートする.
  • ジョブをジョブから取り出す.
  • readyQueueが空であり、現在の時間がJobQueueの最近のリクエストよりも小さい場合、現在の時間はJobQueueの最近のリクエスト時間と同期されます.
  • は、現在よりも早いすべてのタスクをjobQueueから取り出し、処理が必要なreadyQueueに入れる.
  • readyQueueのタスクを処理し、2番目に戻ります.
    • 3番目から2番目に戻る理由は、ジョブの処理が完了すると、処理する時間が経過し、処理するワークロードが最小限になるためです.
    public class 프로그래머스_디스크컨트롤러 {
    /**
     * jobs[i][j] == i ms 에 들어오는 j ms 소요시간 작업 요청.
     *
     *
     * 하드디스크가 작업을 수행하고 있지 않을 때는 먼저 들어온 작업부터 처리.
     *
     * 시간은 0 ~ 1000 까지
     *
     * 각 작업의 소요 시간은 1 ~ 1000 사이     *
     */
    public int solution(int[][] jobs) {
        int time = 0;
        int waitTime = 0;

        int jobCnt = jobs.length;
        PriorityQueue<Job> jobQueue = new PriorityQueue<>();
        PriorityQueue<Ready> readyQueue = new PriorityQueue<>();

        for (int[] job : jobs) {
            int requestTime = job[0];
            int amount = job[1];
            jobQueue.add(new Job(requestTime, amount));
        }

        while (!jobQueue.isEmpty() || !readyQueue.isEmpty()) {
            if (readyQueue.isEmpty() && time < jobQueue.peek().requestTime)
                time = jobQueue.peek().requestTime;
            while (!jobQueue.isEmpty()) {
                if (time >= jobQueue.peek().requestTime) {
                    readyQueue.add(new Ready(jobQueue.poll()));
                }
                else
                    break;
            }

            if (!readyQueue.isEmpty()) {
                Ready ready = readyQueue.poll();
                int endTime = time + ready.amount;
                waitTime += endTime - ready.requestTime;
                time = endTime;
            }
        }


        int answer = waitTime / jobCnt;

        return answer;
    }

    class Ready implements Comparable<Ready>{
        int requestTime;
        int amount;

        public Ready(Job job) {
            this.requestTime = job.requestTime;
            this.amount = job.amount;
        }

        @Override
        public int compareTo(Ready o) {
            return Integer.compare(this.amount, o.amount);
        }

        @Override
        public String toString() {
            return "Ready{" +
                    "requestTime=" + requestTime +
                    ", amount=" + amount +
                    '}';
        }
    }

    class Job implements Comparable<Job>{
        int requestTime;
        int amount;

        public Job(int requestTime, int amount) {
            this.requestTime = requestTime;
            this.amount = amount;
        }

        @Override
        public int compareTo(Job o) {
            return Integer.compare(this.requestTime, o.requestTime);
        }
    }

    public static void main(String[] args) {
        int[][] jobs = 
                {{0, 3}, {1, 9}, {2, 6}};

        new 프로그래머스_디스크컨트롤러().solution(jobs);
    }
}
    9251号:LCS
    電話番号リスト(startswith)