Single-Threaded CPU
Asked at TikTok
Problem
Single-Threaded CPU gives you tasks with an enqueue time and a processing time. A single CPU, whenever idle, picks the available task with the shortest processing time (ties broken by index); if nothing is available, it waits for the next task. Return the order tasks are processed. It is an event simulation driven by a sorted list and a min-heap.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Two kinds of events matter: tasks becoming available (enqueue times) and the CPU finishing a task.
Sort task indices by enqueue time. Keep a pointer into that sorted list and a min-heap of available tasks keyed by (processingTime, index).
Loop: push every task whose enqueue time is <= time. If the heap is empty, jump time forward to the next enqueue time. Otherwise pop the best task, record it, and advance time by its processing time.
The time jump when idle is important — it avoids stepping one unit at a time across long gaps.
Use 64-bit time: processing times up to 10^9 for 10^5 tasks can exceed 32 bits.
Optimal Approach
Step 1: order = indices sorted by enqueueTime.
Step 2: time = 0, i = 0, heap = [], res = [].
Step 3: While len(res) < n:
If heap is empty and time < enqueue[order[i]]: time = enqueue[order[i]].
Push all tasks with enqueue <= time as (proc, idx).
Pop (p, idx), append idx, time += p.
Step 4: Return res.
Time: O(n log n). Space: O(n).
What Trips People Up in Real Interviews
Sorting the tasks and losing their original indices. Sort an index array instead.
Incrementing time by 1 while idle, which is far too slow for large enqueue times.
Tie-breaking by enqueue time instead of index. With equal processing times the smaller index wins.
32-bit overflow on the running time in C++/Java.
Solution Code
import heapq
def getOrder(tasks):
n = len(tasks)
order = sorted(range(n), key=lambda i: tasks[i][0])
heap = []
res = []
time = 0
i = 0
while len(res) < n:
if not heap and time < tasks[order[i]][0]:
time = tasks[order[i]][0]
while i < n and tasks[order[i]][0] <= time:
idx = order[i]
heapq.heappush(heap, (tasks[idx][1], idx))
i += 1
p, idx = heapq.heappop(heap)
res.append(idx)
time += p
return resFrequently Asked Questions
What is the Single-Threaded CPU problem?
Single-Threaded CPU gives you tasks with an enqueue time and a processing time. A single CPU, whenever idle, picks the available task with the shortest processing time (ties broken by index); if nothing is available, it waits for the next task. Return the order tasks are processed. It is an event simulation driven by a sorted list and a min-heap.
How do you solve Single-Threaded CPU?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Single-Threaded CPU?
Single-Threaded CPU is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Single-Threaded CPU?
- Sorting the tasks and losing their original indices. Sort an index array instead.
- Incrementing time by 1 while idle, which is far too slow for large enqueue times.
- Tie-breaking by enqueue time instead of index. With equal processing times the smaller index wins.
- 32-bit overflow on the running time in C++/Java.