Heap_disk controller c++

4853 ワード
queue programmers algorithm heap PriorityQueue テキストリンク

問題は、1つの操作が上記の操作しか実行できないハードディスクに入ると、要求から終了までの時間が最短で平均値が処理されるという問題である.

1.最小稼働時間からのmin heapの実現

    struct compare {
      bool operator() (vector<int>a, vector<int>b) {
          return a[1]>b[1];
      }
    };
    
    priority_queue <vector<int>, vector<vector<int>>, compare> pq;
priority queueを実装する場合、最初のパラメータはキュー内のデータ型を使用し、2番目のパラメータはvectorコンテナを使用し、最後にカスタム比較演算子compareを使用します.
compare比較演算子は,稼働時間の最小から始まるキューを実現するために作成される.
上記のコードでは、aは親ノード、bは現在のノードである.aがbより大きい場合はtrueを返してswapを行う.これを繰り返すと、祖先ノードが最小の要素を占めます.

2.インバウンド時間順にジョブをソートする

sort(jobs.begin(), jobs.end());

3.宣言変数

int total_time = 0; //요청부터 종료까지 각각 소요된 시간의 합
int current_time=0; //현재 작업이 진행되고 있는 시간   
int jobSize=jobs.size();
int job_cnt=0; //몇 번 째 jobs인지 check하기 위한 변수

4.priority queueとjobsリクエストの繰り返し


5.現在時刻(current time)がジョブがジョブに入る時刻(job[job cnt][0])を超え、待ち行列(push)

    if (job_cnt<jobSize && jobs[job_cnt][0]<=current_time) {
        pq.push(jobs[job_cnt++]);
        continue;
    }

6.優先度キューが空でない場合、優先度が最も高いタスク(タスク時間が最も小さいタスク)から実行(pop)を開始します。

    if (!pq.empty()) {
        current_time+=pq.top()[1];
        total_time+=current_time-pq.top()[0];
        pq.pop();
    }
現在時刻(current time)に現在実行するタスクを加えた時刻(pq.top([1]).
合計時間の和(total time)に、現在のタスクが待機している時間が実行を開始した時間を加算します.

7.priority queueが空の場合、現在時刻(current time)を残りのジョブのジョブエントリ時間に変更する(jobs[job cnt][0])

    else {
        current_time=jobs[job_cnt][0];
    }
完全なコード
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> jobs) {
 
    int total_time = 0;
    int current_time=0;    
    int jobSize=jobs.size();
    int job_cnt=0;
  
    struct compare {
      bool operator() (vector<int>a, vector<int>b) {
          return a[1]>b[1];
      }
    };
  
    priority_queue <vector<int>, vector<vector<int>>, compare> pq;
  
    sort(jobs.begin(), jobs.end());

    while (job_cnt<jobSize || !pq.empty()) {
        if (job_cnt<jobSize && jobs[job_cnt][0]<=current_time) {
            pq.push(jobs[job_cnt++]);
            continue;
        }
       
        if (!pq.empty()) {
            current_time+=pq.top()[1];
            total_time+=current_time-pq.top()[0];
            pq.pop();
        }
    
        else {
            current_time=jobs[job_cnt][0];
        }
    }
   
    return total_time/jobSize;
}
翌日
[アルゴリズム]プログラマー-クレーン型綱引きゲーム/Java