プログラムディスクコントローラ


質問する


https://programmers.co.kr/learn/courses/30/lessons/42627

コード#コード#

#include <string>
#include <vector>
#include <queue>
#include<algorithm>
using namespace std;

struct cmp{
    bool operator()(vector<int> a,vector<int> b){        
        return a[1]>b[1];
    }
};
bool compare(vector<int> a,vector<int> b){
    if(a[0]==b[0]) return a[1]<b[1];
    return a[0]<b[0];
}
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time=0;
    int size=jobs.size();
    int cnt=0;
    
    sort(jobs.begin(),jobs.end(),compare);
    vector<int> visit(size,0);
    
    priority_queue<vector<int>,vector<vector<int>>,cmp> pq;
    
    
    for(int i=0;i<size;i++){
        if(visit[i]==1) continue;
        pq.push(jobs[i]);
        visit[i]=1;
        time=jobs[i][0];
        while(!pq.empty()){
           
            time+=pq.top()[1];
            answer+=time-pq.top()[0];
            pq.pop();

            for(int i=0;i<size;i++){
                if(visit[i]==1) continue;
                if(jobs[i][0]<time){
                    pq.push(jobs[i]);
                    visit[i]=1;
                }
                else break;
            }
        }
    }
    
    
    answer/=size;
    return answer;
}

に答える


重要なのは、要求時間の値が現在時間より小さい場合、作業時間の値が現在時間より小さい順に処理してください.
コードは、ジョブがソートされたことを保証しないため、まず要求時間の昇順にソートします.
sort(jobs.begin(),jobs.end(),compare);
jobsに順次アクセスしていない場合は、現在の時間に基づいてリクエスト時間の短いタスクを優先キューに配置して操作できますが、これは実際には説明しにくいです.