How do you solve Single-Threaded CPU on LeetCode?

Single-Threaded CPU (LeetCode #1834) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using a priority queue allows efficient retrieval of the shortest task.

What is the brute force solution for Single-Threaded CPU?

The brute force approach for Single-Threaded CPU is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we simulate the CPU's behavior by checking each task's enqueue time and processing time. We repeatedly look for the next task to process based on the current time, which can be inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Single-Threaded CPU?

Single-Threaded CPU uses the following concepts: Array, Sorting, Heap (Priority Queue). The recommended patterns to study are: Heap, Sorting.

What are the interview tips for Single-Threaded CPU?

Explain your thought process clearly while coding. Discuss edge cases, such as all tasks arriving at the same time. Practice coding with priority queues and heaps before the interview.

What are common mistakes when solving Single-Threaded CPU?

Not handling the case where the CPU is idle correctly. Failing to manage the priority queue properly, leading to incorrect task order.

#1834

Single-Threaded CPU

Medium

ArraySortingHeap (Priority Queue)HeapSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach uses a priority queue (min-heap) to efficiently manage the tasks based on their processing times. This allows us to quickly select the task with the shortest processing time as soon as the CPU is free.

⚙️

Algorithm

3 steps

1Step 1: Create a list of tasks with their original indices and sort them by enqueue time.
2Step 2: Use a min-heap to store tasks based on processing time. As we iterate through the sorted tasks, add tasks to the heap when they become available.
3Step 3: Process tasks from the heap, updating the current time and adding the processed task's index to the result list.

solution.py26 lines

1# Full working Python code
2
3import heapq
4
5def getOrder(tasks):
6    n = len(tasks)
7    indexed_tasks = [(tasks[i][0], tasks[i][1], i) for i in range(n)]
8    indexed_tasks.sort()
9    result = []
10    min_heap = []
11    current_time = 0
12    i = 0
13
14    while i < n or min_heap:
15        while i < n and indexed_tasks[i][0] <= current_time:
16            heapq.heappush(min_heap, (indexed_tasks[i][1], indexed_tasks[i][2]))
17            i += 1
18
19        if min_heap:
20            processing_time, idx = heapq.heappop(min_heap)
21            result.append(idx)
22            current_time += processing_time
23        else:
24            current_time = indexed_tasks[i][0]
25
26    return result

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the tasks and using a priority queue for efficient task retrieval. The space complexity is O(n) for storing the tasks and the heap.

1Using a priority queue allows efficient retrieval of the shortest task.
2Sorting tasks by enqueue time ensures we process them in the correct order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.