Single-Threaded CPU — Solution in Python, Java & C++
Single-Threaded CPU solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Single-Threaded CPU is a medium coding problem on arrays, sorting and heap, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Heap
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
tasks[i] = [enqueueTime, processingTime] means task i becomes available at enqueueTime and takes processingTime to run. The CPU runs one task at a time and never pauses one it has started.
When the CPU is free it picks the available task with the shortest processing time, breaking ties by the smaller index. If nothing is available it idles until something is. Return the order in which the tasks are processed, as a list of indices.
Example 1
Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: At time 3 both tasks 1 and 2 wait; task 2 is shorter.
Example 2
Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: All arrive together, so they run shortest first.
Example 3
Input: tasks = [[1,1]]
Output: [0]
Constraints
tasks.length == n1 <= n <= 10^51 <= enqueueTime, processingTime <= 10^9
Hints for Single-Threaded CPU
Hint 1
Sort the tasks by enqueue time so they can be released in order.
Hint 2
Keep the released-but-unstarted tasks in a min-heap keyed on
(processingTime, index).Hint 3
When the heap is empty, jump the clock forward to the next enqueue time rather than ticking.
How to solve Single-Threaded CPU
Simulate the CPU. Sort by enqueue time, release everything that has arrived by the current clock into a min-heap ordered by processing time then index, and always start the heap's top.
Approach
- Sort the task indices by enqueue time.
- Release every task whose enqueue time is at most the clock.
- If nothing is available, set the clock to the next task's enqueue time and release again.
- Otherwise pop the shortest task, advance the clock by its processing time, and record its index.
Why it works
Jumping the clock straight to the next enqueue time is what keeps this linear rather than tied to the 10^9 time range — the CPU's state only ever changes at an arrival or a completion. The (processingTime, index) key encodes the tie-break directly, so no second comparison is needed after the pop.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Ticking the clock one unit at a time is far too slow at
10^9. - Ties go to the smaller original index, not the smaller position in the sorted order.
- Tasks that arrive while one is running must be released before the next pick.
Reference solution
Python
from typing import List
import heapq
def getOrder(tasks: List[List[int]]) -> List[int]:
n = len(tasks)
order = sorted(range(n), key=lambda i: tasks[i][0])
heap = []
out = []
at = 0
time = 0
while len(out) < n:
while at < n and tasks[order[at]][0] <= time:
i = order[at]
heapq.heappush(heap, (tasks[i][1], i))
at += 1
if not heap:
time = tasks[order[at]][0]
continue
proc, i = heapq.heappop(heap)
time += proc
out.append(i)
return outJava
public static int[] getOrder(int[][] tasks) {
int n = tasks.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(tasks[a][0], tasks[b][0]));
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> {
if (tasks[a][1] != tasks[b][1]) return Integer.compare(tasks[a][1], tasks[b][1]);
return a - b;
});
int[] out = new int[n];
int cnt = 0, at = 0;
long time = 0;
while (cnt < n) {
while (at < n && tasks[order[at]][0] <= time) heap.add(order[at++]);
if (heap.isEmpty()) {
time = tasks[order[at]][0];
continue;
}
int pick = heap.poll();
time += tasks[pick][1];
out[cnt++] = pick;
}
return out;
}C++
vector<int> getOrder(vector<vector<int>>& tasks) {
int n = (int) tasks.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return tasks[a][0] < tasks[b][0]; });
auto cmp = [&](int a, int b) {
if (tasks[a][1] != tasks[b][1]) return tasks[a][1] > tasks[b][1];
return a > b;
};
priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);
vector<int> out;
int at = 0;
long long time = 0;
while ((int) out.size() < n) {
while (at < n && tasks[order[at]][0] <= time) heap.push(order[at++]);
if (heap.empty()) {
time = tasks[order[at]][0];
continue;
}
int pick = heap.top();
heap.pop();
time += tasks[pick][1];
out.push_back(pick);
}
return out;
}JavaScript
var getOrder = function(tasks) {
var n = tasks.length, i;
var order = [];
for (i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return tasks[a][0] - tasks[b][0]; });
// Min-heap of task indices ordered by (processingTime, index).
var heap = [];
var less = function(a, b) {
if (tasks[a][1] !== tasks[b][1]) return tasks[a][1] < tasks[b][1];
return a < b;
};
var push = function(v) {
heap.push(v);
var j = heap.length - 1;
while (j > 0) {
var p = (j - 1) >> 1;
if (!less(heap[j], heap[p])) break;
var t = heap[p]; heap[p] = heap[j]; heap[j] = t;
j = p;
}
};
var pop = function() {
var top = heap[0];
var last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
var j = 0;
for (;;) {
var l = 2 * j + 1, r = l + 1, s = j;
if (l < heap.length && less(heap[l], heap[s])) s = l;
if (r < heap.length && less(heap[r], heap[s])) s = r;
if (s === j) break;
var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
j = s;
}
}
return top;
};
var out = [];
var at = 0, time = 0;
while (out.length < n) {
while (at < n && tasks[order[at]][0] <= time) { push(order[at]); at++; }
if (heap.length === 0) {
time = tasks[order[at]][0];
continue;
}
var pick = pop();
time += tasks[pick][1];
out.push(pick);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms