Process Tasks Using Servers — Two-Heap Scheduling Interview Pattern

Problem Statement#

You have n servers and m tasks. Task i arrives at second i and runs for tasks[i] seconds. Assign each task to the free server with smallest weight (ties: smallest index). If no server is free, the task waits.

Constraints:

• 1 <= servers.length, tasks.length <= 2 * 10^5
• 1 <= servers[i], tasks[i] <= 2 * 10^5
• Output: array where ans[i] is the server assigned to task i

Input:  servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]

Input:  servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]

Why This Problem Matters#

LeetCode 1882 is a hard-medium that frequently shows up in Google, Amazon, and Microsoft interviews. It tests whether you can coordinate two priority queues to simulate a real scheduling system — exactly the kind of design pattern used in load balancers and job dispatchers.

The two-heap pattern is a recurring theme in priority queue interview problems. You see it in K closest points, sliding window median, and now in scheduling. Mastering it pays dividends across the heap FAANG interview canon.

The Core Insight#

You need two heaps. The free heap holds available servers ordered by (weight, index). The busy heap holds running servers ordered by (free_time, weight, index). At each second, drain busy servers whose free_time <= now back into the free heap, then assign.

If the free heap is empty when a task arrives, fast-forward now to the earliest busy server's free time.

Visual Dry Run#

servers = [3,3,2], tasks = [1,2,3,2,1,2]

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        free = [(w, i) for i, w in enumerate(servers)]
        heapq.heapify(free)
        busy = []
        ans = [0] * len(tasks)
        now = 0
 
        for t, duration in enumerate(tasks):
            now = max(now, t)
            if not free and busy and busy[0][0] > now:
                now = busy[0][0]
            while busy and busy[0][0] <= now:
                _, w, idx = heapq.heappop(busy)
                heapq.heappush(free, (w, idx))
            w, idx = heapq.heappop(free)
            ans[t] = idx
            heapq.heappush(busy, (now + duration, w, idx))
        return ans

// Uses a simple binary-heap helper for clarity
class MinHeap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[i], this.h[p]) < 0) {
                [this.h[i], this.h[p]] = [this.h[p], this.h[i]];
                i = p;
            } else break;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0, n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let m = i;
                if (l < n && this.cmp(this.h[l], this.h[m]) < 0) m = l;
                if (r < n && this.cmp(this.h[r], this.h[m]) < 0) m = r;
                if (m === i) break;
                [this.h[m], this.h[i]] = [this.h[i], this.h[m]];
                i = m;
            }
        }
        return top;
    }
    peek() { return this.h[0]; }
    get size() { return this.h.length; }
}
 
var assignTasks = function(servers, tasks) {
    const free = new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1]);
    const busy = new MinHeap((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    servers.forEach((w, i) => free.push([w, i]));
    const ans = new Array(tasks.length);
    let now = 0;
    for (let t = 0; t < tasks.length; t++) {
        now = Math.max(now, t);
        if (free.size === 0 && busy.size && busy.peek()[0] > now) now = busy.peek()[0];
        while (busy.size && busy.peek()[0] <= now) {
            const [, w, idx] = busy.pop();
            free.push([w, idx]);
        }
        const [w, idx] = free.pop();
        ans[t] = idx;
        busy.push([now + tasks[t], w, idx]);
    }
    return ans;
};

Time: O((m + n) log n) — each server enters/exits each heap O(1) times across all m tasks. Space: O(n) — both heaps together hold at most n entries.

Common Mistakes#

• Forgetting to fast-forward now when no servers are free; this causes infinite waits or wrong assignments.
• Drainage order: you must drain busy first, then pop from free.
• Storing only weight in busy heap and losing index — break ties incorrectly.
• Comparing free time tuples without including weight tiebreaker for the busy heap.
• Using a plain queue instead of a heap for free servers — O(n) per pick blows the limit.

Interview Tips#

• State the two-heap design out loud before coding; interviewers love clear partitioning.
• Walk through one full assignment cycle on paper with 3 servers and 4 tasks.
• Mention that now is monotonic and only jumps forward when no server is free.
• Call out the amortized analysis: each server has O(log n) heap work per assignment.

Follow-up Questions#

• What if tasks can preempt low-priority running tasks? Hint: you need a third heap of running tasks by priority.
• What if servers can fail mid-task? Hint: rebroadcast the task to the free heap with a generation counter.
• What if you must minimize total weighted completion time? Hint: this becomes a scheduling theory problem (SRPT).
• How would you scale to 10 million servers? Hint: shard servers by weight bucket.
• Can you do it lock-free in a real system? Hint: per-bucket SPSC queues with a coordinator.

Key Takeaways#

• LeetCode 1882 Process Tasks Using Servers is solved by two coordinated heaps in O((m+n) log n).
• Free heap orders by (weight, index); busy heap orders by (free_time, weight, index).
• Fast-forward now only when free is empty to avoid empty-pop bugs.
• Task arrival at time i is a hard constraint — now = max(now, i).
• Drain busy heap before assigning each task.
• This pattern generalizes to job dispatching and load balancers in production systems.
• The two-heap idiom is the most reused trick in priority queue interview rounds.