디스크 컨트롤러

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs,(a,b)->a[0]-b[0]);
        
        PriorityQueue<int[]>pq=new  PriorityQueue<>((a,b)->a[1]-b[1]);
        
        int idx=0;
        int done=0;
        int totaltime=0;
        int now=0;
        
        while(done<jobs.length){
            
            while(idx<jobs.length && jobs[idx][0]<=now){
                pq.add(jobs[idx++]);
            }
            
            // 그 자리로 바로 이동  [[5,9],[12,3]]
            if(pq.isEmpty()){
                now=jobs[idx][0];
            }
            else{
                // 끝나는 시간을 기준으로 요청시간을 뺀다. 
                int[]job=pq.poll();
                now+=job[1];
                totaltime+=(now-job[0]);
                done++;
            }
        }
        
        return totaltime/jobs.length;
    }
}

 

 

디스크 컨트롤러 개인적으로 처음 도착한 순서대로 정렬하고 만약 그렇지 않으면 코드가 반복적으로 되돌아 가면서 확인해서 O(n^2) 이라는 시간 복잡도가 나온다. (도착한 시간대로 정렬해주자)

포인터가 있고 작업의 개수를 세주는 변수도 있어야 한다.

 

PriortityQueue<int[]> 요청시간 ,소요시간 이렇게 2개의 값을 써야 할 때 무조건 필요하다. 

그리고 소요시간을 기준으로 정렬하고 현재 시간을 기준으로  요청시간이 짧다면 계속 넣은 다음 정렬해서 뽑아 내는 이 아이디어가 중요한 문제인 거 같다. (어렵지는 않다.)