1834. Single-Threaded CPU

Single-Threaded CPU (LeetCode 1834) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

• NeetCode 250 · #117 of 250 · Heap / Priority Queue

How to solve Single-Threaded CPU

Single-Threaded CPU is a Scheduling and Minimum Cost problem, part of Heap (Priority Queue) Patterns. Solve scheduling and optimization problems using priority queue with greedy approach.

Work towards the solution in these steps:

1. To simulate the problem we first need to note that if at any point in time there are no enqueued tasks we need to wait to the smallest enqueue time of a non-processed element
2. We need a data structure like a min-heap to support choosing the task with the smallest processing time from all the enqueued tasks

The reference solution runs in O(nlogn) time and O(n) space.

The Single-Threaded CPU solution and editorial walks through the full approach with reference code.

Problem statement

You are given n​​​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the i​​​​​​th​​​​ task will be available to process at enqueueTimei and will take processingTimei to finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

- If the CPU is idle and there are no available tasks to process, the CPU remains idle.

- If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.

- Once a task is started, the CPU will process the entire task without stopping.

- The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1] Explanation: The events go as follows: - At time = 1, task 0 is available to process. Available tasks = {0}. - Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}. - At time = 2, task 1 is available to process. Available tasks = {1}. - At time = 3, task 2 is available to process. Available tasks = {1, 2}. - Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}. - At time = 4, task 3 is available to process. Available tasks = {1, 3}. - At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}. - At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}. - At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] Output: [4,3,2,0,1] Explanation: The events go as follows: - At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}. - Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}. - At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}. - At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}. - At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}. - At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}. - At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

- tasks.length == n

- 1 <= n <= 105

- 1 <= enqueueTimei, processingTimei <= 109

Topics and companies

Topics: Array, Sorting, Heap (Priority Queue).

How to practise Single-Threaded CPU on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Single-Threaded CPU in the code editor, or read the Single-Threaded CPU editorial for a worked solution with its approach and complexity analysis.

Where Single-Threaded CPU sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
• The full DSA patterns sheet

Problems related to Single-Threaded CPU

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

• Furthest Building You Can Reach — Medium, same subpattern
• IPO — Hard, same subpattern
• Longest Happy String — Medium, same subpattern
• Maximum Average Pass Ratio — Medium, same subpattern
• Meeting Rooms II — Medium, same subpattern
• Meeting Rooms III — Hard, same subpattern

Single-Threaded CPU FAQ