프로그래머스
[프로그래머스] 디스크 컨트롤러 (javascript, 우선순위큐, 그리디)
해랑쓰
2021. 3. 11. 18:26
728x90
반응형
첫 작업은 도착 시간이 빠른 순으로, 그 다음부터는 이미 도착한 것들 중에서 작업 시간이 짧은 것을
큐에 넣어서 진행한다. (매번 재정렬을 해준다)
function solution(jobs) {
var answer = 0;
jobs.sort((a,b)=>a[0]-b[0]);// 첫 작업은 가장 먼저오는 걸로
const pq=[];//우선 순위 큐 (시작이 가능한 일들이 들어가며 작업시간 오름차순정렬됨)
let i=0, time=0;
while(i<jobs.length || pq.length!=0){// 우선순위큐가 비어야 종료됨
//우선 순위 큐 넣는 작업
if(i<jobs.length && jobs[i][0]<=time){
pq.push(jobs[i++]);
pq.sort((a,b)=>a[1]-b[1]);
continue;//다음 것도 넣어보러 간다~~
}
//현재 도착한 작업이 없을 때
if(pq.length===0){
time=jobs[i][0]; //첫 작업을 현재 시간으로 바꿔준다.
}else{
const [start,work]=pq.shift();
answer+=time+work-start;
time+=work;
}
}
return parseInt(answer/jobs.length);
}
728x90
반응형