MediumArraySortingHeapUpdated Sep 2026

1834. Single-Threaded CPU

Asked at TikTok

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given n tasks, numbered 0 to n-1. Each task is a pair tasks[i] = [enqueueTime, processingTime]: the task becomes available at enqueueTime, and it needs processingTime units of work to finish.

There is one CPU, and it can run only one task at a time. When the CPU is free, it looks at all tasks that have already become available and picks the one with the smallest processing time. If two tasks have the same processing time, it picks the one with the smaller index. If no task is available yet, the CPU does nothing until the next task appears. Once a task starts, it runs to completion without interruption, and the CPU can start the next task at the exact moment the previous one ends.

Return the list of task indices in the order the CPU processes them. The answer has length n and contains every index exactly once.

Who runs next?

tasksenqueueprocess012312243241Tasks 1 and 2 are both available at time 3ready queuetask 1 (p=4)task 2 (p=2)01The CPU picks task 2 — shorter processing time wins
At time 3 the CPU is free and tasks 1 and 2 are waiting; it picks task 2 because its processing time is smaller.

Constraints

  • ●1 <= tasks.length <= 10^5
  • ●tasks[i] = [enqueueTime_i, processingTime_i]
  • ●1 <= enqueueTime_i, processingTime_i <= 10^9

Examples

Example 1
Inputtasks = [[1,2],[2,4],[3,2],[4,1]]
Output[0,2,3,1]
WhyAt time 1 only task 0 is ready, so it starts and runs until time 3. By then tasks 1 and 2 are ready; task 2 has the shorter processing time (2 vs 4), so it goes next and ends at time 5. Task 3 is ready by then and has processing time 1, the shortest, so it runs until time 6. Only task 1 is left, so
Example 2
Inputtasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output[4,3,2,0,1]
WhyAll five tasks appear at time 7, so the CPU just keeps picking the shortest remaining one. The processing times are 2, 4, 5, 10, 12, which belong to indices 4, 3, 2, 0, 1 — exactly the output order.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Two kinds of events matter: tasks becoming available (enqueue times) and the CPU finishing a task.

2

Sort task indices by enqueue time. Keep a pointer into that sorted list and a min-heap of available tasks keyed by (processingTime, index).

3

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.

4

The time jump when idle is important — it avoids stepping one unit at a time across long gaps.

5

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).

Sort, then simulate with a min-heap

sort indices by enqueue timepush all tasks with enqueue <= timepop (process, index) from heaptime += process, record indexThe main loop: feed the heap, then run the best taskheap at time 3(2, task 2)(4, task 1)← topThe heap is ordered by (processing time, index), sothe top is the next taskif heap empty: time = next enqueue timekey = (processingTime, index)time += processingTime
A pointer feeds newly available tasks into the heap; the heap always hands back the best task to run next.
ComplexityTime O(n log n)Space O(n)Sorting the indices costs O(n log n), and each task enters and leaves the heap once, which costs O(log n) per task.

What Trips People Up in Real Interviews

1

Sorting the tasks and losing their original indices. Sort an index array instead.

2

Incrementing time by 1 while idle, which is far too slow for large enqueue times.

3

Tie-breaking by enqueue time instead of index. With equal processing times the smaller index wins.

4

32-bit overflow on the running time in C++/Java.

Solution Code

O(n log n) time
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 res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.