NeetCode #539LC-1834MediumHeap / Priority QueueNC 250
← Back to All Problems#539 · #1834 · Single-Threaded CPU(单线程 CPU)
📌 Problem Statement & Constraints
You are given
tasks where tasks[i] = [enqueueTime, processingTime]. A single-threaded CPU picks, at each idle moment, the available task with the smallest processing time (ties broken by index). Return the order in which the tasks are processed. Constraints: 1 <= tasks.length <= 10^5.💡 Core Algorithmic Approaches
- Sort the tasks by enqueue time to know which become available when.
- At each step, push all tasks whose enqueue time is at most the current time into a min-heap keyed by
(processingTime, index). - Pop the smallest, advance the clock by its processing time, and record its index.
- When the heap is empty, jump the clock to the next task's enqueue time rather than incrementing it.
💻 Benchmark Python3 Implementation
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
import heapq
n = len(tasks)
order = sorted(range(n), key=lambda i: (tasks[i][0], tasks[i][1]))
h = [] # (processingTime, index)
res = []
time = 0
i = 0
while i < n or h:
if not h and time < tasks[order[i]][0]:
time = tasks[order[i]][0] # jump to the next arrival
while i < n and tasks[order[i]][0] <= time:
idx = order[i]
heapq.heappush(h, (tasks[idx][1], idx))
i += 1
proc, idx = heapq.heappop(h)
time += proc
res.append(idx)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort plus O(n) heap operations.
💾 Space Complexity
O(n) for the heap and the sorted order.
⚠️ Interview Pitfalls & Follow-ups
- Incrementing the clock one unit at a time: the enqueue times can be up to 10^9.
- Sorting by processing time only: the availability constraint would be violated.
- Tie-breaking by index: the heap key must be
(processingTime, index), which a tuple provides automatically. - Forgetting to jump the clock when idle: the loop would spin without progress.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.