Problem statement

https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/

Solution

The idea is to use two heaps:

  1. aval is heap for avaliable servers, where we keep id’s
  2. busy is heap of busy servers at the moment, where we keep pair (ending time, id).

When new request arrives, first we need to check all servers which become free: we check busy[0][0] <= a for this, then we push this server id to aval. Note, that we want keep in available ids numbers form i to i + k - 1, so each time we choose from available servers starting from value i. Then we extract j: index of server we need to allocate to new task and add its ending time to busy heap. Also update res[j]. For me tricky part is i + (x-i)%k here, alternative way is to keep sortedlist, see next solution.

Complexity

Time complexity is O(n log k), space is O(k)

Code

class Solution:
    def busiestServers(self, k, A, B):
        aval, busy, res = list(range(k)), [], [0]*k 
        for i, (a, b) in enumerate(zip(A, B)):
            while busy and busy[0][0] <= a:
                _, x = heappop(busy)
                heappush(aval, i + (x-i)%k)
            if not aval: continue
                
            j = heappop(aval) % k
            heappush(busy, (a + b, j))
            res[j] += 1
                
        a = max(res)
        return [i for i in range(k) if res[i] == a]

Solution 2

So, the idea is to keep sorted list of indexes and each time look for smallest element bigger than i % k: number of severs we want to start with. If we did not found such element, take 0-th.

Complexity

Complexity is the same O(n log k) for time and O(k) for space, but works slower due to heavy sorted list.

Code

from sortedcontainers import SortedList

class Solution:
    def busiestServers(self, k, A, B):
        aval, busy, res = SortedList(range(k)), [], [0]*k
        
        for i, (a, b) in enumerate(zip(A, B)):
            while busy and busy[0][0] <= a:
                _, x = heappop(busy)
                aval.add(x)
            if not aval: continue
                
            idx = aval.bisect_left(i % k) % len(aval)
            act = aval.pop(idx)
            res[act] += 1
            heappush(busy, (a+b, act))
            
        a = max(res)
        return [i for i in range(k) if res[i] == a]