“This is the 24th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

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] 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.Copy the code

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.
Copy the code

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.
Copy the code

Example 4:

Input: k = 3, concatenated =,2,3,4,8,9,10 [1], the load =,2,10,3,1,2,2 [5] the Output: [1]Copy the code

Example 5:

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

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.
Copy the code

parsing

There are k servers, numbered from 0 to K-1, that handle multiple requests simultaneously. Each server has unlimited computing power, but cannot handle more than one request at a time. Assign requests to servers based on a specific algorithm:

  • The ith (index from 0) request arrives
  • If all servers are busy, the request is discarded (not processed at all)
  • If the (I % k) server is available, the request is assigned to that server
  • Otherwise, assign the request to the next available server (around the list of servers and starting at 0 if necessary), for example, if the ith server is busy, try to assign the request to the (I +1) server, then the (I +2) server, and so on.

Given a strictly increasing array of positive integers arrival, 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 required to complete). The goal is to find the busiest server. A server is considered the busiest if it successfully handles the highest number of requests of all servers. Returns a list containing the ids of the busiest servers. Ids can be returned in any order.

The main idea of the solution is to maintain two lists: one is the list of free servers and the other is the list of servers that are executing requests. Each time a new request is received, if free is empty, the request can be discarded. If it is not empty, find the free server from (I % k) back, if not, find the free server from 0.

There are two key areas need to pay attention to, when one is free to initialize and buzy choose can automatically sort of class, another is in free find free server had better have built-in function, if there is no dichotomy is used to find, if the two steps to deal with bad timeout easily, my code is just right, time consuming and very serious.

answer

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]Copy the code

The results

Runtime: 5120 ms, Faster than 10.00% of Python online submissions for Find Servers That Handled Most of Requests. Memory Usage: Submissions in Python online for Find Servers That Handled Most of Requests.Copy the code

Original link: leetcode.com/problems/fi…

Your support is my biggest motivation