---
# System prepended metadata

title: 1882. Process Tasks Using Servers
tags: [mock interview, 面試]

---

# 1882. Process Tasks Using Servers

Bob wants to buy insurance. 
He goes to insurance company, lie in a queue, to buy insurance.
There are N insurance agent that can server for customer.
Each agent has a constant work speed to handle customers.

Please return how much time needed for Bob to wait.

insuranceAgent = [5, 3, 1] # time
# insuranceAgent[i] >= 1, length n 10**6

people = 5
# length p 10**6


5....X
3..X
111X
   ^
# map = idxToTime
# heap -> fast finish time
# (5, 0) (3, 1) (1, 2) # endTime, idx. -> freeAgent
# [(5, 0) (3, 1) (1, 2)] ->  [(1, 2), (3, 1), (5, 0)]
[(1, 2), (3, 1), (5, 0)] p=5-3 = 2

p=4 (1, 2) -> (2, 2) # t+t, idx
[(2, 2), (3, 1), (5, 0)]

p=5 (2, 2) -> (3, 2) # 2+1
[(3, 2), (3, 1), (5, 0)] -> (endTime, idx)


[1, 1000]

p = 5

1 1 1 1 1 ->5

1 1 1 1 -> 4
return 3
# consume people
```python=
#agentServeTime = [5, 3, 1] # time
#waitingPeopel = 5
def findWaitTime(agentServeTime, waitingPeople):
    # edge case

    if waitingPeople < len(agentServeTime):
        return 0

    # heap
    priorityQueue = []
    # init agents to people
    for i in range(len(agentServeTime)):
        heappush(priorityQueue, [agentServeTime[i], i])
    
    # priorityQueue
    # [(1, 2), (3, 1), (5, 0)]
    waitingPeople -= len(agentServeTime)
    # waitingPeople = 5-3=2
    
    # consume people
    # p4
    # p5
    # O(MlogN)
    while waitingPeople > 0:
        # O(logN)
        endTime, idx = heappop(priorityQueue) # (2, 2)
        nextEndTime += agentServeTime[idx] # (2+1, 2)
        heappush(priorityQueue, [nextEndTime, idx])
        # p4 [ (3, 1), (3, 2), (5, 0)]
        waitingPeople -= 1 # 0
    
    return priorityQueue[0][0] # earliest end time for Bob 
    
    # M : waitingPeople
    # N : length of agentServeTime
    # Time Complexity: O(MlogN)

```

