1606. Find Servers That Handled Most Number of Requests

Loading...LeetCode

从题目给的example示意图就看出来，需要一直维护servers的工作状态，对每个新来的request检查可用的server，然后记录server处理request的次数。有点像meeting rooms的感觉。

253. Meeting Rooms II

• 维护 servers工作状态，其实本质上是分别维护 working servers 和 available servers

• 维护 working servers，需要一个基于时间的工作序列，谁有 request 要处理了，就加进来；谁先把request 处理完，就把谁先弹出序列。直接用heap最小堆就可以，按照 request 的结束时间来排，每新来一个request，就把结束时间早于当前时间的给弹出来，加入available servers.

• 维护available servers就比较麻烦，可以直接用 set，但题目寻找ideal server的规则是一个基于 sorted array 的，python 的 set 本身无法保证sorted，需要使用SortedSet来实现。

Leetcode 上也有用另一个 heap 来维护 available servers 的。

Python

from sortedcontainers import SortedSet

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        working = []  # use heap to maintain the working server queue
        available = SortedSet([i for i in range(k)])  # use sorted set to maintain the available servers
        count = [0 for _ in range(k)]
        
        for i in range(len(arrival)):
            start = arrival[i]
            time = load[i]
            ideal = i % k
            
            # see the newly avaliable servers
            while working and working[0][0] <= start:
                _, offWork = heapq.heappop(working)
                available.add(offWork)
                
            # no avaliable server, drop the request
            if len(available) == 0: continue
                
            # find the available server whose index >= ideal index
            idx = available.bisect_left(ideal)
            # if the ideal index exceed current largest available server index, loop back to the first one
            server = available.pop(idx) if idx < len(available) else available.pop(0)
            # add the count, push the handled one into the working queue
            count[server] += 1
            heapq.heappush(working, (start+time, server))
            
        target = max(count)
        return [i for i, j in enumerate(count) if j == target]