MediumNo. 1834
Single-Threaded CPU — LeetCode 1834 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Sorting, Heap (Priority Queue)
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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 ith 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.
Example
- Input
- tasks = [[1,2],[2,4],[3,2],[4,1]]
- Output
- [0,2,3,1]
- Explanation
- The events go as follows:
Python solution
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
for i, task in enumerate(tasks):
task.append(i)
tasks.sort()
ans = []
q = []
n = len(tasks)
i = t = 0
while q or i < n:
if not q:
t = max(t, tasks[i][0])
while i < n and tasks[i][0] <= t:
heappush(q, (tasks[i][1], tasks[i][2]))
i += 1
pt, j = heappop(q)
ans.append(j)
t += pt
return ansComplexity
- Time
- O(n × log n)where n is the number of tasks
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1834. Single-Threaded CPU is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0506 | Relative Ranks | Easy |
| 0912 | Sort an Array | Medium |
| 0973 | K Closest Points to Origin | Medium |
| 1094 | Car Pooling | Medium |
Frequently asked questions
- How hard is LeetCode 1834. Single-Threaded CPU?
LeetCode 1834. Single-Threaded CPU is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1834. Single-Threaded CPU?
The Python solution on this page runs in O(n × log n), where n is the number of tasks.
- What is the space complexity of LeetCode 1834. Single-Threaded CPU?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1834. Single-Threaded CPU cover?
LeetCode 1834. Single-Threaded CPU is tagged Array, Sorting and Heap (Priority Queue) on LeetCode.