Single-Threaded CPU
Medium · Heap / Priority Queue · Explanation and code example
Sorting + Min-Heap (Optimal)
How it works
This solution optimizes memory by not modifying the original tasks array. Instead of copying task data, we sort an array of indices by enqueue time. The heap stores only indices and uses the original tasks array for comparisons. This approach is more memory efficient while maintaining the same time complexity.
Steps
- Create an array of indices
[0, 1, 2, ..., n-1]and sort it based on the tasks' enqueue times. - Initialize
timeto0, and create a min-heap that compares indices by their task's processing time (then byindexfor ties). - Iterate through sorted indices:
- Push indices of tasks that have become available onto the heap.
- If the heap is empty and tasks remain, jump
timeforward. - Otherwise, pop the best task, update
time, and record the result.
- Return the execution order.
Complexity
- Time complexity:
O(n log n) - Space complexity:
O(n)
Things to watch for
Losing Track of Original Indices
After sorting tasks by enqueue time, the original indices get shuffled. Failing to preserve and correctly reference the original task indices leads to returning the wrong execution order. Always attach the original index to each task before any sorting operation.
Incorrect Heap Comparison Priority
The heap must prioritize by processing time first, then by original index for ties. Reversing this order or forgetting the tiebreaker causes incorrect task selection when multiple tasks have the same processing time.
Integer Overflow in Time Calculation
When summing processing times, the cumulative time can exceed the 32-bit integer range for large inputs. Using a long or 64-bit integer for the time variable prevents overflow errors that lead to incorrect task availability checks.
Not Handling CPU Idle Time
When no tasks are available in the heap but tasks remain pending, the CPU must jump forward in time to the next task's enqueue time. Forgetting this case causes an infinite loop or incorrect scheduling when there are gaps between task arrivals.
Inefficient Available Task Selection
Using a list and sorting it each iteration instead of a proper min-heap results in O(n^2 log n) time complexity. The heap data structure is essential for efficiently selecting the minimum processing time task in O(log n) time.
Python code example
from typing import List
import heapq
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
n = len(tasks)
indices = list(range(n))
indices.sort(key=lambda i: (tasks[i][0], i))
class Task:
def __init__(self, idx):
self.idx = idx
def __lt__(self, other):
if tasks[self.idx][1] != tasks[other.idx][1]:
return tasks[self.idx][1] < tasks[other.idx][1]
return self.idx < other.idx
minHeap = []
res = []
time = i = 0
while minHeap or i < n:
while i < n and tasks[indices[i]][0] <= time:
heapq.heappush(minHeap, Task(indices[i]))
i += 1
if not minHeap:
time = tasks[indices[i]][0]
else:
next_task = heapq.heappop(minHeap)
time += tasks[next_task.idx][1]
res.append(next_task.idx)
return res
C++ code example
// C++ Solution
class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
int n = tasks.size();
vector<int> indices(n);
iota(indices.begin(), indices.end(), 0);
sort(indices.begin(), indices.end(), [&](int a, int b) {
return tasks[a][0] < tasks[b][0] ||
(tasks[a][0] == tasks[b][0] && a < b);
});
auto comp = [&](int a, int b) {
return tasks[a][1] > tasks[b][1] ||
(tasks[a][1] == tasks[b][1] && a > b);
};
priority_queue<int, vector<int>, decltype(comp)> minHeap(comp);
vector<int> result;
long long time = 0;
int i = 0;
while (!minHeap.empty() || i < n) {
while (i < n && tasks[indices[i]][0] <= time) {
minHeap.push(indices[i]);
i++;
}
if (minHeap.empty()) {
time = tasks[indices[i]][0];
} else {
int nextIndex = minHeap.top();
minHeap.pop();
time += tasks[nextIndex][1];
result.push_back(nextIndex);
}
}
return result;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.