Process Tasks Using Servers

Process Tasks Using Servers

What is this problem about?

The Process Tasks Using Servers problem gives you a list of servers (each with a weight) and tasks (each arriving at time i with processing time tasks[i]). Assign each task to the free server with the smallest weight (ties broken by index), waiting if all servers are busy. This coding problem uses two priority queues: one for free servers and one for busy servers. The array and heap interview pattern is the core.

Why is this asked in interviews?

Lyft, Twitter, Amazon, TikTok, and Google ask this because it tests multi-heap simulation — a pattern common in scheduling systems, load balancers, and resource management. Managing the transition between free and busy server pools is the key challenge.

Algorithmic pattern used

Two min-heaps. free_heap = (weight, index) for available servers. busy_heap = (finish_time, weight, index) for occupied servers. For each task i at time i: first, move all servers from busy_heap that finished by time i to free_heap. If free_heap is not empty, assign task to the smallest-weight free server. Else, pop the earliest-finishing server from busy_heap (advance time to its finish time), reassign.

Example explanation

servers=[3,3,2], tasks=[1,2,3,2,1,2]. (weights indexed 0,1,2)

• Task 0 at t=0: free=[( 2,2),(3,0),(3,1)]. Assign to server 2 (weight=2). busy=[(1,2,2)].
• Task 1 at t=1: busy server 2 finishes at t=1 → move to free. free=[(2,2),(3,0),(3,1)]. Assign to server 2. Continue... Result: [2,2,0,2,1,2].

Common mistakes candidates make

• Not moving finished servers to free_heap before each task assignment.
• Using a single heap (can't efficiently track both pools).
• Incorrect tiebreaking (weight first, then index).
• Not advancing time when all servers are busy.

Interview preparation tip

Two-heap scheduling problems follow a consistent pattern: "free" heap for available resources, "busy" heap for occupied resources sorted by release time. At each event: (1) free up finished resources, (2) assign the best available resource. Practice this pattern on: "meeting rooms II," "task scheduler," "minimum servers." The dual-heap structure is the essential tool for online scheduling simulations.