#1882

Medium

auto_awesomeArray plus Heap (Priority Queue)

LeetCode Problem Workspace

Process Tasks Using Servers

Assign tasks to servers efficiently using arrays and heaps, resolving ties by weight and index while tracking availability precisely.

array heap priority queue

Problem Statement

You are given two integer arrays: servers, where servers[i] is the weight of the i-th server, and tasks, where tasks[j] is the time required for the j-th task. Each task arrives in order, one per second, and must be assigned to a server immediately if possible.

At each second, the next task is added to a queue. While the queue is not empty and servers are free, assign the front task to the available server with the smallest weight; if multiple servers share the same weight, pick the smallest index. Track busy servers to know when they become free for future tasks.

Examples

Example 1

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

Output: [2,2,0,2,1,2]

Events in chronological order go as follows:

At second 0, task 0 is added and processed using server 2 until second 1.
At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
At second 2, task 2 is added and processed using server 0 until second 5.
At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
At second 4, task 4 is added and processed using server 1 until second 5.
At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Example 2

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

Output: [1,4,1,4,1,3,2]

Events in chronological order go as follows:

At second 0, task 0 is added and processed using server 1 until second 2.
At second 1, task 1 is added and processed using server 4 until second 2.
At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4.
At second 3, task 3 is added and processed using server 4 until second 7.
At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9.
At second 5, task 5 is added and processed using server 3 until second 7.
At second 6, task 6 is added and processed using server 2 until second 7.

Constraints

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 105
1 <= servers[i], tasks[j] <= 2 * 105

Solution Approach

Use a Min-Heap for Available Servers

Maintain a min-heap of available servers sorted by weight and index. When a task arrives, pop the top server to assign the task. This ensures the smallest weight and index rules are respected for each assignment.

Track Busy Servers in a Heap

Keep a separate min-heap of busy servers where each entry stores the time the server becomes free. At each second, move any servers that finished tasks back into the available heap. This handles overlapping tasks and ensures the simulation progresses correctly.

Simulate Task Queue Efficiently

Iterate through each second, adding tasks to the queue. While tasks remain and servers are free, assign tasks from the queue using the heaps. Update server free times and repeat until all tasks are processed. Using heaps avoids scanning all servers repeatedly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on heap operations for n servers and m tasks, leading to O(m log n) for assignments and free-time updates. Space complexity is O(n + m) due to heaps and tracking the task queue.

What Interviewers Usually Probe

Notice the need for two heaps: available and busy servers.
Ask about handling tie-breaking by server index for same weight.
Expect discussion on time simulation per task and efficient queue processing.

Common Pitfalls or Variants

Common pitfalls

Failing to update server availability at the correct second can misassign tasks.
Not maintaining tie-breaking by index leads to incorrect output for servers with equal weight.
Assigning tasks without considering the queue order causes timing mismatches.

Follow-up variants

Instead of smallest weight, assign to server with largest weight first.
Process tasks with variable arrival intervals instead of one per second.
Allow preemption of tasks on servers with higher weight if a lighter server becomes available.

FAQ

What is the main pattern in Process Tasks Using Servers?

The core pattern is Array plus Heap (Priority Queue), using heaps to track free and busy servers while assigning tasks in order.

How do I handle tie-breaking between servers with the same weight?

Always select the server with the smaller index when multiple servers share the same weight, using the heap to enforce this order.

Can tasks arrive at variable times instead of one per second?

Yes, but the heap simulation must adjust by advancing the current time to the next task arrival or the earliest server free time.

What data structures are essential for an efficient solution?

Two min-heaps: one for available servers sorted by weight and index, and one for busy servers sorted by free time, are critical for efficiency.

Why does the problem require simulating each second?

Simulating time ensures tasks are assigned in the correct order and servers become available at the proper moments, preserving the queue logic.

terminal

Solution

Solution 1: Priority Queue (Min-Heap)

We use a min-heap $\textit{idle}$ to maintain all idle servers, where each element is a tuple $(x, i)$ representing the $i$-th server with weight $x$. We use another min-heap $\textit{busy}$ to maintain all busy servers, where each element is a tuple $(w, s, i)$ representing the $i$-th server that will be idle at time $w$ with weight $s$. Initially, we add all servers to $\textit{idle}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        idle = [(x, i) for i, x in enumerate(servers)]
        heapify(idle)
        busy = []
        ans = []
        for j, t in enumerate(tasks):
            while busy and busy[0][0] <= j:
                _, s, i = heappop(busy)
                heappush(idle, (s, i))
            if idle:
                s, i = heappop(idle)
                heappush(busy, (j + t, s, i))
            else:
                w, s, i = heappop(busy)
                heappush(busy, (w + t, s, i))
            ans.append(i)
        return ans

Continue Practicing

#1878 get biggest three rhombus sums in a grid #1912 design movie rental system #1851 minimum interval to include each query