LeetCode 1834: Single-Threaded CPU
Problem Description
Explanation
To solve this problem, we need to simulate the CPU processing tasks based on the given rules. We can use a priority queue to keep track of the available tasks sorted by their processing times. We iterate through the tasks based on their enqueue times and process them accordingly.
- Create a priority queue to store tasks based on their processing times and indices.
- Sort the tasks based on their enqueue times.
- Iterate through the tasks:
- Enqueue tasks that are available at the current time into the priority queue.
- If the CPU is idle and there are available tasks in the queue, process the task with the shortest processing time.
- Update the current time and continue until all tasks are processed.
Time Complexity: O(n log n) where n is the number of tasks. Space Complexity: O(n) for the priority queue.
Solutions
import java.util.*;
class Solution {
public int[] getOrder(int[][] tasks) {
int n = tasks.length;
int[] order = new int[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
Queue<Integer> availableTasks = new LinkedList<>();
for (int i = 0; i < n; i++) {
tasks[i] = new int[] {i, tasks[i][0], tasks[i][1]}; // {index, enqueueTime, processingTime}
}
Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
int time = tasks[0][1];
int idx = 0;
while (idx < n || !pq.isEmpty()) {
while (idx < n && tasks[idx][1] <= time) {
pq.offer(new int[] {tasks[idx][0], tasks[idx][2]});
idx++;
}
if (pq.isEmpty()) {
time = tasks[idx][1];
continue;
}
int[] task = pq.poll();
order[idx] = task[0];
time += task[1];
availableTasks.add(task[0]);
}
return order;
}
}Loading editor...