MediumNo. 1882
Process Tasks Using Servers — LeetCode 1882 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Heap (Priority Queue)
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the ith server, and tasks[j] is the time needed to process the jth task in seconds.
Example
- Input
- servers = [3,3,2], tasks = [1,2,3,2,1,2]
- Output
- [2,2,0,2,1,2]
- Explanation
- Events in chronological order go as follows:
Python solution
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 ansComplexity
- Time
- O((n + m) log n)where n is the number of servers and m is the number of tasks
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1882. Process Tasks Using Servers is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1878 | Get Biggest Three Rhombus Sums in a Grid | Medium |
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0373 | Find K Pairs with Smallest Sums | Medium |
| 0407 | Trapping Rain Water II | Hard |
| 0506 | Relative Ranks | Easy |
Frequently asked questions
- How hard is LeetCode 1882. Process Tasks Using Servers?
LeetCode 1882. Process Tasks Using Servers is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1882. Process Tasks Using Servers?
The Python solution on this page runs in O((n + m) log n), where n is the number of servers and m is the number of tasks.
- What is the space complexity of LeetCode 1882. Process Tasks Using Servers?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1882. Process Tasks Using Servers cover?
LeetCode 1882. Process Tasks Using Servers is tagged Array and Heap (Priority Queue) on LeetCode.