문제
풀이
종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할때 평균시간이 얼마나 되는지 리턴하면 되는 문제 이다. 입력으로 주어지는 배열에서 각 배열의 원소도 배열으로 구성되어있는데, 0번째는 시작 시간, 1번째는 종료 시간으로 구성되어있다
이부분은 시작이 빠른 것부터 실행 하면 가장 빠른 걸린 시간을 구할 수 있다.
그리고 두번째 조건이 있는데 종료가 빠른 task부터 먼저 실행하면 더욱 빠르다.
이때문에 priorityQueue 에 넣고 연산전에 이런 정렬 작업을 진행하는 것이다
물론 Comparator를 여러개 사용해도 되지만 PriortyQueue의 성질을 이용하면 더 빨리 끝나는 연산이기 때문에 써먹을 필요가 있다. 입력할때는 배열의 sort를 사용하여 시작이 빠른것부터 넣어주는대신 꺼낼때는 종료가 빠른 것부터 꺼낼수가 있기 때문이다.
...
Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
...그러고 나서 모든 작업을 차례대로 실행하면서 종료 시간을 total 시간에 넣고 평균을 낼 수 있다.
// 요청 개수가 jobs의 개수만큼 실행되어야 한다
while (requestCnt < jobs.length) {
// 현재 까지 실행될 수 있는 데이터들을 큐에 넣고 실행 대기 한다
while (index < jobs.length && jobs[index][0] <= current) {
pq.add(jobs[index++]);
}
// 실행할 것이 없을때까지 실행한다
if (pq.isEmpty()) {
// 현재 시간을 셋팅해준다
current = job[index][0];
} else {
//
int[] temp = pq.poll();
// 실행시간 = 종료 시간 + 현재 시간 - 시작 시간
answer += temp[1] + current - temp[0];
// 현재 시간에 작업 종료 시간을 더해주면 그 다음에 시작할 작업의 시간이다
current += temp[1];
// 실행한 작업의 개수가 증가됨
requestCnt++;
}
}
return (int) Math.floor(answer/jobs.length);우선순위 큐가 익숙하지가 않아서 많이 헤맸던 문제이다.
전체 코드
develop life