연구 시설에서 방금 새 수퍼 컴퓨터를 받았습니다. 한 번에 여러 가지 작업을 수행 할 수 있지만, 각 작업이 결과를 내기까지 걸리는 시간을 알고있는 경우에만 가능합니다.프로그램의 시간 복잡성 작업을 예약하는 자바 스크립트
이 슈퍼 시간 단위의 시간을 측정하고, 다음과 같이 동작한다 :
처리해야되는 작업 큐에 배치된다. 대기열의 맨 위에있는 작업에는 정확하게 1 시간 단위의 CPU 시간이 주어집니다. 완료되지 않은 경우 대기열 뒤쪽에 배치됩니다. 대기열의 작업 재조정은 특수 처리 장치에서 관리하므로 추가 CPU 시간이 필요하지 않습니다. 작업을 처리 대기열에 제출했으며 결과 준비가 완료 될 때까지 기다려야하는 시간을 확인하려고합니다.
taskQueue가 양의 정수 배열로 주어지면 taskQueue [i]는 결과를 제공하기 위해 대기열의 i 번째 작업에 남은 CPU 시간의 시간 단위 수를 나타내며 양의 정수 n은 사용자의 현재 색인으로 나타냅니다. taskQueue (0 기반)에서 작업을 완료 할 때까지 기다려야하는 시간 단위 수를 찾으십시오. 우리는 1 개 시간 단위로 큐 상태를 통과하면 작업 대기열은 = 3, 1, 2 및 N = 2 출력 태스킹 (작업 대기열, N) = 5 이어야 예
[3,1,2 '] -> [2', 2] -> [2,1 '] -> [1', 1] -> [1] 작업에 '으로 표시되어 있습니다. 작업 대기열은 = [1, 2, 3, 1, 2 및 N = 0, 출력 태스킹 (작업 대기열, N) = 1 입력/출력되어야 용
[기한] 4000ms (JS) [input] array.integer taskQueue
i 번째 정수는 결과를 제공하기 위해 대기열의 i 번째 작업에 남겨진 CPU 시간의 시간 단위 수를 나타냅니다.
보장 제약 : 1 ≤ taskQueue.length ≤ 105 1 ≤ 작업 대기열 [I] ≤ 109
는 는 는[입력] 정수 N
작업 대기열에서 태스크의 인덱스 (0 계).
보장 된 제약 조건 : 0 ≤ n < taskQueue.length.
[출력]
당신이 당신의 작업이 완료 될 때까지 기다릴 필요가 시간 단위의 수
를 integer64.function multitasking(taskQueue, n) {
let queue = new Queue(taskQueue,n);
while(queue.data.length) {
queue.runTask();
}
return queue.count;
}
function Queue(data,n) {
this.data = [...data];
this.taskIndex = n;
this.count = 0;
this.requeue = function() {
let firstvalue = this.data[0];
if(this.taskIndex) {
this.taskIndex--;
} else if(!firstvalue) {
this.data = [];
return;
} else {
this.taskIndex = this.data.length-1;
}
if(firstvalue) {
this.data.push(firstvalue);
}
this.data.shift();
}
this.runTask = function() {
this.data[0]--;
this.count++;
this.requeue();
}}
이 대부분의 경우 잘 작동 :
이
내가 작성한 코드입니다. 그러나 시간 복잡성은 높습니다. 에 대한. 예.멀티 태스킹 ([10000000001000000000], 1) 이것은 4000ms 미만으로는 해결되지 않습니다. 누구나 시간 복잡성을 줄일 수 있습니까?