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

  1. Two heaps: a free-server min-heap keyed by (weight, index) and a busy min-heap keyed by (freeTime, weight, index).
  2. For each task, advance the clock to max(clock, taskIndex); if no server is free, jump the clock to the earliest free time.
  3. Move every server whose free time has arrived back into the free heap.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems