leetcode 1606. Find Servers That Handled Most Number of Requests（python）

語言: CN / TW / HK
時間 2021-11-24 10:15:04

「這是我參與11月更文挑戰的第24天，活動詳情檢視：2021最後一次更文挑戰」

描述

You have k servers numbered from 0 to k-1 that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

  • The ith (0-indexed) request arrives.
  • If all servers are busy, the request is dropped (not handled at all).
  • If the (i % k)th server is available, assign the request to that server.
  • Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the ith server is busy, try to assign the request to the (i+1)th server, then the (i+2)th server, and so on.

You are given a strictly increasing array arrival of positive integers, where arrival[i] represents the arrival time of the ith request, and another array load, where load[i] represents the load of the ith request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

Example 1:

Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 
Output: [1] 
Explanation:
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.

Example 2:

Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation:
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.

Example 3:

Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles a single request, so they are all considered the busiest.

Example 4:

Input: k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]
Output: [1]

Example 5:

Input: k = 1, arrival = [1], load = [1]
Output: [0]

Note:

1 <= k <= 10^5
1 <= arrival.length, load.length <= 10^5
arrival.length == load.length
1 <= arrival[i], load[i] <= 10^9
arrival is strictly increasing.

解析

根據題意，有 k 個伺服器，編號從 0 到 k-1 ，用於同時處理多個請求。每個伺服器都有無限的計算能力，但一次不能處理多個請求。根據特定演算法將請求分配給伺服器：

  • 第 i 個（ 從 0 開始索引）請求到達
  • 如果所有伺服器都忙，則請求將被丟棄（根本不處理）
  • 如果第 (i % k) 個伺服器可用，則將請求分配給該伺服器
  • 否則，將請求分配給下一個可用的伺服器（環繞伺服器列表並在必要時從 0 開始），例如，如果第 i 個伺服器繁忙，則嘗試將請求分配給第 (i+1) 個伺服器，然後是第 (i+2) 個伺服器，依此類推。

給定一個嚴格遞增的正整數陣列 arrival ，其中 arrival[i] 表示第 i 個請求的到達時間，以及另一個數組 load ，其中 load[i] 表示第 i 個請求的負載（完成所需的時間）。目標是找到最繁忙的伺服器。如果伺服器在所有伺服器中成功處理的請求數量最多，則該伺服器被認為是最繁忙的。返回包含最繁忙伺服器的 ID 的列表。可以按任何順序返回 ID。

題目很繁雜，但是理解之後也比較簡單，解法的主要思想是維護兩個列表，一個是空閒伺服器列表 free ，另一個是正在執行請求的伺服器列表 buzy ，每次得到一個新的請求的時候，如果 free 為空，丟棄該請求即可，如果不為空從第 (i % k) 個伺服器中向後找空閒伺服器，如果沒有則從第 0 個開始找空閒伺服器。

有兩個關鍵的地方需要注意，一個是初始化 free 和 buzy 的時候選用能自動排序的類，另一個是在 free 中找空閒伺服器時最好有內建函式，如果沒有則用二分法進行找，如果這兩個步驟處理不好很容易超時，我的程式碼也是剛好過，耗時還是很嚴重。

解答

from sortedcontainers import SortedList
class Solution(object):
    def busiestServers(self, k, arrival, load):
        """
        :type k: int
        :type arrival: List[int]
        :type load: List[int]
        :rtype: List[int]
        """
        free = SortedList([i for i in range(k)])
        buzy = SortedList([],key=lambda x:-x[1])
        count = {i:0 for i in range(k)}
        for i,start in enumerate(arrival):
            while(buzy and buzy[-1][1]<=start):
                pair = buzy.pop()
                free.add(pair[0])
            if not free: continue
            id = self.findServer(free, i%k)
            count[id] += 1
            free.remove(id)
            buzy.add([id, start+load[i]])
        result = []
        MAX = max(count.values())
        for k,v in count.items():
            if v == MAX:
                result.append(k)
        return result
    def findServer(self, free, id):
        idx = bisect.bisect_right(free, id-1)
        if idx!=len(free):
            return free[idx]
        return free[0]

執行結果

Runtime: 5120 ms, faster than 10.00% of Python online submissions for Find Servers That Handled Most Number of Requests.
Memory Usage: 38.6 MB, less than 50.00% of Python online submissions for Find Servers That Handled Most Number of Requests.

原題連結：http://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/

您的支援是我最大的動力

「」
「」