NeetCode #541LC-1882MediumHeap / Priority Queue
← Back to All Problems#541 · #1882 · Process Tasks Using Servers(使用服务器处理任务)
📌 Problem Statement & Constraints
You are given
servers (where servers[i] is the weight of server i) and tasks (where tasks[j] is the time to process task j). Task j arrives at time j. A free server is chosen by smallest weight, then smallest index; if none is free, the task waits for the earliest available. Return the server index assigned to each task. Constraints: 1 <= n, m <= 2 * 10^5.💡 Core Algorithmic Approaches
- Two heaps: a free-server min-heap keyed by
(weight, index)and a busy min-heap keyed by(freeTime, weight, index). - For each task, advance the clock to
max(clock, taskIndex); if no server is free, jump the clock to the earliest free time. - Move every server whose free time has arrived back into the free heap.
- Pop the best free server, record it, and push it into the busy heap with
clock + duration.
💻 Benchmark Python3 Implementation
class Solution:
def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
import heapq
free = [(servers[i], i) for i in range(len(servers))]
heapq.heapify(free) # (weight, index)
busy = [] # (freeTime, weight, index)
res = []
clock = 0
for j, dur in enumerate(tasks):
clock = max(clock, j) # the task is not available before time j
if not free:
clock = busy[0][0] # jump to the earliest release
while busy and busy[0][0] <= clock:
ft, w, i = heapq.heappop(busy)
heapq.heappush(free, (w, i))
w, i = heapq.heappop(free)
res.append(i)
heapq.heappush(busy, (clock + dur, w, i))
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + m) log n): each server and task costs a constant number of heap operations.
💾 Space Complexity
O(n) for the two heaps.
⚠️ Interview Pitfalls & Follow-ups
- Not jumping the clock when no server is free: the loop would assign tasks to busy servers.
- Advancing the clock by one unit: the times can be up to 2 * 10^5, so jumping to the release time is required for the stated complexity.
- Ordering the free heap by index first: the primary key is the weight, with the index as the tie-break.
- Forgetting
clock = max(clock, j): a task cannot start before it arrives.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.