1834. Single-Threaded CPU / TypeScript

You are given n​​​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the i​​​​​​th​​​​ task will be available to process at enqueueTimei and will take processingTimei to finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

• If the CPU is idle and there are no available tasks to process, the CPU remains idle.
• If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
• Once a task is started, the CPU will process the entire task without stopping.
• The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

 

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

 

출처 : https://leetcode.com/problems/single-threaded-cpu/description/

 

 

풀이

function getOrder(tasks: number[][]): number[] {
    const availableTasks = new PriorityQueue({ compare: (a, b) => a.processingTime - b.processingTime || a.index - b.index });
    const remainingTasks = tasks.map((t, i) => ({ availableAt: t[0], processingTime: t[1], index: i })).sort((a, b) => b.availableAt - a.availableAt );

    let timer = remainingTasks[remainingTasks.length - 1].availableAt;

    const answer = [];

    while (remainingTasks.length || availableTasks.size()) {
        while (remainingTasks.length && timer >= remainingTasks[remainingTasks.length - 1].availableAt) {
            availableTasks.enqueue(remainingTasks.pop());
        }

        if (availableTasks.size()) {
            const currentTask = availableTasks.dequeue();
            timer += currentTask.processingTime;
            answer.push(currentTask.index);
        } else if (remainingTasks.length) {
            timer = remainingTasks[remainingTasks.length - 1].availableAt;
        }
    }

    return answer;
};

 

주어진 작업 목록(tasks)을 처리할 순서를 결정하는 함수

 

 

• 우선순위 큐 준비:
  • availableTasks라는 우선순위 큐를 생성.
  • 이 큐는 작업의 처리 시간(processingTime)이 짧은 순서대로, 처리 시간이 같다면 인덱스(index)가 작은 순서대로 정렬
• 남은 작업 목록 준비:
  • tasks 배열을 availableAt (시작 가능 시간)과 processingTime (처리 시간), 그리고 인덱스(index)를 포함한 객체로 변환
  • 변환된 작업 목록을 availableAt 기준으로 내림차순으로 정렬
• 타이머 초기화:
  • timer를 남은 작업 목록 중 가장 마지막 작업의 시작 가능 시간으로 초기화
• 작업 처리 루프:
  • 남은 작업 목록(remainingTasks) 또는 우선순위 큐(availableTasks)에 작업이 남아있는 동안 반복
  • 현재 timer 값이 남은 작업 목록의 마지막 작업의 시작 가능 시간보다 크거나 같은 경우, 해당 작업을 availableTasks 큐에 추가
  • 만약 우선순위 큐에 작업이 있으면, 처리 시간이 가장 짧은 작업을 꺼내서(dequeue) timer에 그 작업의 처리 시간을 더하고, 결과 배열(answer)에 해당 작업의 인덱스를 추가
  • 만약 우선순위 큐가 비어있고 남은 작업 목록에 작업이 남아있다면, timer를 남은 작업 목록의 마지막 작업의 시작 가능 시간으로 업데이트
• 결과 반환:
  • 모든 작업을 처리한 후, 결과 배열(answer)을 반환

 

 

예시

tasks = [[1, 2], [2, 4], [3, 2], [4, 1]];

 

 

각 배열 요소는 [availableAt, processingTime] 형식

즉, tasks[0]는 시작 가능 시간이 1이고, 처리 시간이 2

 

함수 실행 과정:

1. 우선순위 큐 준비:
   • 우선순위 큐인 availableTasks를 생성.
2. 남은 작업 목록 준비:
   • 각 작업을 객체로 변환하여 remainingTasks에 저장

remainingTasks = [
  { availableAt: 1, processingTime: 2, index: 0 },
  { availableAt: 2, processingTime: 4, index: 1 },
  { availableAt: 3, processingTime: 2, index: 2 },
  { availableAt: 4, processingTime: 1, index: 3 }
];

 

이 목록을 시작 가능 시간(availableAt) 기준으로 내림차순으로 정렬

remainingTasks = [
  { availableAt: 4, processingTime: 1, index: 3 },
  { availableAt: 3, processingTime: 2, index: 2 },
  { availableAt: 2, processingTime: 4, index: 1 },
  { availableAt: 1, processingTime: 2, index: 0 }
];

 

   3. 타이머 초기화:

• timer를 남은 작업 목록 중 가장 마지막 작업의 시작 가능 시간인 1로 초기화

   4.작업 처리 루프:

• availableTasks와 remainingTasks에 작업이 남아있는 동안 반복.
• remainingTasks에서 timer 값보다 작거나 같은 availableAt 값을 가진 작업을 availableTasks에 추가

 

첫 번째 반복:

• timer는 1이고, remainingTasks의 마지막 작업의 availableAt이 1이므로, 해당 작업을 availableTasks에 추가

availableTasks = [{ availableAt: 1, processingTime: 2, index: 0 }];
remainingTasks = [
  { availableAt: 4, processingTime: 1, index: 3 },
  { availableAt: 3, processingTime: 2, index: 2 },
  { availableAt: 2, processingTime: 4, index: 1 }
];

 

availableTasks에서 처리 시간이 가장 짧은 작업을 꺼내서 처리. 타이머를 2만큼 증가:

timer = 3;
answer = [0];

 

두 번째 반복:

• timer는 3이고, remainingTasks의 마지막 작업의 availableAt이 2이므로, 해당 작업을 availableTasks에 추가

availableTasks = [{ availableAt: 2, processingTime: 4, index: 1 }];
remainingTasks = [
  { availableAt: 4, processingTime: 1, index: 3 },
  { availableAt: 3, processingTime: 2, index: 2 }
];

 

timer는 3이고, remainingTasks의 마지막 작업의 availableAt이 3이므로, 해당 작업을 availableTasks에 추가

availableTasks = [
  { availableAt: 3, processingTime: 2, index: 2 },
  { availableAt: 2, processingTime: 4, index: 1 }
];
remainingTasks = [{ availableAt: 4, processingTime: 1, index: 3 }];

 

availableTasks에서 처리 시간이 가장 짧은 작업을 꺼내서 처리. 타이머를 2만큼 증가

timer = 5;
answer = [0, 2];

 

세 번째 반복:

• timer는 5이고, remainingTasks의 마지막 작업의 availableAt이 4이므로, 해당 작업을 availableTasks에 추가

availableTasks = [
  { availableAt: 4, processingTime: 1, index: 3 },
  { availableAt: 2, processingTime: 4, index: 1 }
];
remainingTasks = [];

 

availableTasks에서 처리 시간이 가장 짧은 작업을 꺼내서 처리. 타이머를 1만큼 증가

timer = 6;
answer = [0, 2, 3];

 

네 번째 반복:

• availableTasks에서 처리 시간이 가장 짧은 작업을 꺼내서 처리. 타이머를 4만큼 증가

timer = 10;
answer = [0, 2, 3, 1];

 

결과 반환:

• 모든 작업을 처리한 후, 결과 배열(answer)을 반환