# 1606. Find Servers That Handled Most Number of Requests

{% embed url="<https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/>" %}

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

![](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-MIw3FWmzlk9arn6kQ-N%2F-MIzkG682jFw7KFRQGwU%2Fimage.png?alt=media\&token=a9a5adc4-7aa8-4719-8b8f-090b25765a6a)

{% content-ref url="253.-meeting-rooms-ii" %}
[253.-meeting-rooms-ii](https://xuqiangwen1994.gitbook.io/practice/253.-meeting-rooms-ii)
{% endcontent-ref %}

* 维护 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](https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/discuss/876883/Python-using-only-heaps) 上也有用另一个 heap 来维护 available servers 的。

{% tabs %}
{% tab title="Python" %}

```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]
```

{% endtab %}
{% endtabs %}
