Process Tasks Using Servers

You are given two arrays: servers where servers[i] is the weight of the i-th server, and tasks where tasks[j] is the processing time of the j-th task. Task j becomes available at time j. When a task is available, assign it to the free server with the smallest weight. If multiple free servers share the smallest weight, pick the one with the smallest index. If no server is free, wait until the earliest server finishes and assign the task then. Return an array where ans[j] is the index of the server that handles task j.

This is LeetCode 1882: Process Tasks Using Servers, a medium problem that teaches the two-heap scheduling pattern. You maintain one heap for free servers and another for busy servers, and the heaps do all the heavy lifting of tracking availability and priority.

The approach

The trick is to maintain two min-heaps:

1. Free heap: sorted by (weight, index). This lets you always grab the lightest available server in O(log n) time.
2. Busy heap: sorted by (finish_time, weight, index). This tells you which server finishes next so you can move it back to the free heap.

At each time step t (or whenever you need to assign a task), you first check the busy heap and move any servers whose finish time has passed back to the free heap. Then you pop the best server from the free heap and assign the task.

If the free heap is empty when you need to assign a task, you fast-forward time to the earliest finish time in the busy heap. This avoids looping one unit at a time through idle periods.

The code

import heapq

def assignTasks(servers, tasks):
    free = [(w, i) for i, w in enumerate(servers)]
    heapq.heapify(free)
    busy = []  # (finish_time, weight, index)
    ans = [0] * len(tasks)

    for j, duration in enumerate(tasks):
        t = j  # task j is available at time j

        # Release servers that have finished by time t
        while busy and busy[0][0] <= t:
            finish, w, i = heapq.heappop(busy)
            heapq.heappush(free, (w, i))

        # If no server is free, fast-forward to the next finish time
        if not free:
            t = busy[0][0]
            while busy and busy[0][0] <= t:
                finish, w, i = heapq.heappop(busy)
                heapq.heappush(free, (w, i))

        # Assign the task to the best free server
        w, i = heapq.heappop(free)
        ans[j] = i
        heapq.heappush(busy, (t + duration, w, i))

    return ans

Here is what each section does:

1. Build the free heap from all servers as (weight, index) tuples. Python's heapq is a min-heap, so the lightest server (with the smallest index as tiebreaker) will always be on top.
2. For each task j, set the current time t = j since task j becomes available at time j.
3. Release finished servers: pop everything from the busy heap whose finish time is <= t and push it back onto the free heap.
4. Handle no free servers: if the free heap is empty, jump time forward to busy[0][0] (the earliest finish) and release all servers finishing at that time.
5. Pop the best free server, record the assignment in ans[j], and push the server onto the busy heap with its new finish time t + duration.

Visual walkthrough

Notice how server 2 (weight 2) dominates the assignments. Because it has the lowest weight, it gets picked every time it is free. Servers 0 and 1 (both weight 3) only get tasks when server 2 is busy. When servers 0 and 1 tie on weight, the tiebreaker goes to the smaller index, so server 0 gets picked first.

Complexity analysis

Each task triggers at most one push and one pop on each heap. Each heap has at most n elements, so each operation is O(log n). Over m tasks, that gives O(m log n). Building the initial free heap is O(n). Releasing servers across all tasks is O(n log n) total because each server can be released at most once per assignment. Combining these gives O((m + n) log n).

Space is O(n) because the two heaps together hold exactly n servers at all times (each server is in one heap or the other).

Building blocks

Two-heap scheduling pattern

The core idea is splitting resources into two pools: "available" and "in use." A min-heap on each pool lets you efficiently find the best available resource and the soonest-to-finish busy resource. You will see this pattern in:

• Meeting Rooms II: one heap for ongoing meetings (sorted by end time), one counter or heap for free rooms.
• IPO: one heap for affordable projects, one for locked projects sorted by capital requirement.
• Task Scheduler: tracking cooldown expiration for task types.

The skeleton is always the same: release resources from the busy heap when their time is up, then pick the best resource from the free heap.

Time-driven simulation

Instead of ticking time forward one unit at a time, you jump directly to the next interesting event. In this problem, the interesting events are: (a) a new task becomes available, and (b) a server finishes its current task. When no server is free, you fast-forward to busy[0][0] rather than looping through empty time steps. This is what makes the solution O((m + n) log n) rather than O(max_time * n).

This event-driven approach appears in many simulation problems. Whenever you catch yourself writing a loop that increments time by 1, ask whether you can skip ahead to the next meaningful event instead.

Edge cases

• Single server: all tasks queue up on server 0. The busy heap always has one entry, and the free heap alternates between empty and having one element.
• More servers than tasks: many servers stay idle forever. The algorithm handles this naturally since it only pops from the free heap when there is a task to assign.
• All tasks arrive at t=0 with duration 1: every server gets one task at t=0, and any remaining tasks get assigned at t=1 when the first batch finishes.
• Tasks with very long durations: causes the fast-forward logic to kick in. If task 0 takes 1,000,000 units and there is only one server, tasks 1 through 999,999 all wait, and time jumps to the finish time each round.
• All servers have equal weight: tiebreaking is purely by index. Server 0 gets assigned first, then server 1, and so on. The heaps still work correctly because tuples compare element by element.

From understanding to recall

You have walked through the two-heap approach and it clicks. Two heaps, release finished servers, pop the lightest free one, fast-forward if needed. But in an interview, you need to write it without hesitation. The details matter: remembering to include weight and index in the busy heap tuple so servers return to the free heap in the right order, and remembering the fast-forward logic when the free heap is empty.

Spaced repetition drills those details into long-term memory. You write the solution from scratch, check it, and revisit it at increasing intervals. After a few rounds, the two-heap skeleton is automatic. You see "assign resources by priority, track availability" and the code flows out without fumbling over tuple ordering or edge cases.

Related posts

• Cheapest Flights Within K Stops - Priority queue for optimal selection under constraints
• Find Kth Largest XOR Coordinate Value - Heap-based top-K tracking
• Average Waiting Time - Another task scheduling simulation problem