⚡Flashcard Drill➔
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

  1. Sort the tasks by enqueue time to know which become available when.
  2. At each step, push all tasks whose enqueue time is at most the current time into a min-heap keyed by (processingTime, index).
  3. Pop the smallest, advance the clock by its processing time, and record its index.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems