AlgoMaster Logo

Process Tasks Using Servers

mediumFrequency5 min readUpdated June 23, 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 takes a task, it becomes busy for tasks[j] seconds. The challenge is tracking which servers are free and which are busy, and knowing exactly when busy servers become free again.

At any moment the solution needs two answers: which free server has the smallest weight (and smallest index on a tie), and which busy server becomes free the soonest. Both are min-heap queries, which is what drives the efficient approach below.

Key Constraints:

  • 1 <= n, m <= 2 * 10^5 → With up to 200,000 servers and 200,000 tasks, scanning all servers for every task is O(m n) = 4 10^10 operations, too slow within typical time limits. This rules out the brute force at full scale and points to O(m log n).
  • 1 <= servers[i], tasks[j] <= 2 * 10^5 → Task durations reach 200,000 seconds, so the timeline can stretch far beyond m. Simulating second by second is not viable, so time must advance by jumping to the next event.

Approach 1: Brute Force Simulation

Intuition

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 advance time to that moment.

For every task this scans all n servers to find the best free one, which is slow but correct, and it makes the rules concrete before optimizing.

Algorithm

  1. Create an array freeAt of size n, initialized to 0. freeAt[i] stores the second when server i becomes free.
  2. For each task j (arriving at second j):
    • Set the current time t = max(j, earliest freeAt value among all servers).
    • Scan all servers. Among those with freeAt[i] <= t, find the one with the smallest weight (ties broken by smallest index).
    • Assign the task to that server: set ans[j] = bestServer and update freeAt[bestServer] = t + tasks[j].
  3. Return ans.

Example Walkthrough

1Initialize: freeAt=[0,0,0], servers=[3,3,2]. All servers free at time 0.
0
0
1
0
2
0
1/7

Code

The cost comes from the two linear scans per task. Replacing those scans with priority queues makes finding the lightest free server O(log n) instead of O(n).

Approach 2: Two Heaps (Free + Busy)

Intuition

The brute force repeats the same two queries for every task: which free server has the smallest weight, and which busy server finishes earliest. Both are min-heap operations.

Maintain two heaps. A free heap stores available servers, ordered by (weight, index). A busy heap stores occupied servers, ordered by finish time. When a task arrives, move any servers whose finish time has passed from the busy heap back to the free heap, then pop the top of the free heap to assign the task.

One case needs care. If no server is free when a task arrives, advance time to the earliest finish time in the busy heap rather than stepping through empty seconds. That earliest finish releases at least one server, so the free heap is non-empty afterward and the task can be assigned at that moment.

Algorithm

  1. Build a free heap with all servers as (weight, index) pairs.
  2. Create an empty busy heap that will store (finishTime, weight, index) entries.
  3. For each task j:
    • Set time = max(j, top of busy heap's finish time) if the free heap is empty. Otherwise, time = j.
    • Move all servers from the busy heap whose finish time <= time back to the free heap.
    • Pop the top of the free heap. That's the assigned server.
    • Push (time + tasks[j], weight, index) onto the busy heap.
    • Record ans[j] = server index.
  4. Return ans.

Example Walkthrough

1Initialize: free heap = [(2,2), (3,0), (3,1)], busy heap = []
[_, _, _, _, _, _]
1/7

Code