Process Tasks Using Servers
Last Updated: April 4, 2026
Understanding the Problem
This problem is a scheduling simulation. Tasks arrive one per second (task j arrives at second j), and each task must be assigned to the lightest available server (breaking ties by index). Once a server picks up a task, it becomes busy for tasks[j] seconds. The challenge is efficiently tracking which servers are free and which are busy, and knowing exactly when busy servers will become free again.
The key observation: at any moment, we need to quickly answer two questions. First, which free server has the smallest weight (and index)? Second, which busy server will become free the soonest? Both of these scream "priority queue."
Key Constraints:
1 <= n, m <= 2 * 10^5→ With up to 200,000 servers and 200,000 tasks, we need something better than O(m n). Scanning all servers for every task would be O(m n) = 4 * 10^10 operations, far too slow.1 <= servers[i], tasks[j] <= 2 * 10^5→ Task durations can be up to 200,000 seconds, so the simulation timeline can stretch far beyondm.- Given these constraints, we need O(m log n) or better, which points toward a heap-based approach.
Approach 1: Brute Force Simulation
Intuition
The most direct approach: simulate the process exactly as described. For each task, scan all servers to find the lightest free one. Track each server's busy-until time in an array. When no server is free, find the one that finishes earliest and fast-forward time.
This is straightforward but slow. For every task, we potentially scan all n servers to find the best free one.
Algorithm
- Create an array
freeAtof sizen, initialized to 0.freeAt[i]stores the second when serveribecomes free. - For each task
j(arriving at secondj):
a. Set the current time t = max(j, earliest freeAt value among all servers).
b. Scan all servers. Among those with freeAt[i] <= t, find the one with the smallest weight (ties broken by smallest index).
c. Assign the task to that server: set ans[j] = bestServer and update freeAt[bestServer] = t + tasks[j].
- Return
ans.
Example Walkthrough
Code
- Time Complexity: O(m * n). For each of the m tasks, we scan all n servers twice: once to find the earliest free time and once to find the best free server.
- Space Complexity: O(n). We use an array of size n to track when each server becomes free.
For each task, we linearly scan all servers to find the lightest free one. What if we used a priority queue so that finding the lightest free server was O(log n) instead of O(n)?
Approach 2: Two Heaps (Free + Busy)
Intuition
The brute force scans all servers for every task. But notice: we're always asking the same two questions. "Which free server has the smallest weight?" and "Which busy server finishes earliest?" Both of these are classic min-heap queries.
Here's the idea: maintain two heaps. A free heap stores available servers, ordered by (weight, index). A busy heap stores occupied servers, ordered by their finish time. When a new task arrives, we first move any servers whose finish time has passed from the busy heap back to the free heap. Then we pop the top of the free heap to assign the task.
There's one subtle detail. If no server is free when a task arrives, we can't just wait around. We fast-forward time to the earliest finish time in the busy heap. This avoids simulating empty seconds one by one.
The two heaps perfectly model the two pools of servers. The free heap always gives us the best available server in O(log n), and the busy heap tells us the next server to become available. By moving servers between heaps as time progresses, we maintain an accurate picture of the system state at every moment.
The fast-forward trick is crucial. Without it, we'd need to simulate every second, which could be up to 4 * 10^10 time steps. Instead, we only process events at meaningful moments: when a task arrives or when a server becomes free.
Algorithm
- Build a free heap with all servers as
(weight, index)pairs. - Create an empty busy heap that will store
(finishTime, weight, index)entries. - For each task
j:
a. Set time = max(j, top of busy heap's finish time) if the free heap is empty. Otherwise, time = j.
b. Move all servers from the busy heap whose finish time <= time back to the free heap.
c. Pop the top of the free heap. That's the assigned server.
d. Push (time + tasks[j], weight, index) onto the busy heap.
e. Record ans[j] = server index.
- Return
ans.
Example Walkthrough
Code
- Time Complexity: O(m log n). Each task involves at most one push and one pop from each heap. Heap operations on a heap of size n cost O(log n). Over m tasks, that's O(m log n).
- Space Complexity: O(n). Both heaps together hold exactly n servers at all times, since each server is in exactly one heap.