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

「 This is my participation 11 The fourth of the yuegengwen challenge 24 God , Check out the activity details ：2021 One last more challenge 」

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 i^th (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 i^th 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 i^th request, and another array load, where load[i] represents the load of the i^th 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.
 Copy 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 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 code 

Example 4:

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

Example 5:

Input: k = 1, arrival = [1], load = [1]
Output: [0]
 Copy 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 code 

analysis

According to the meaning , Yes k Servers , Number from 0 To k-1 , Used to process multiple requests at the same time . Every server has unlimited computing power , But you can't process multiple requests at once . Assign the request to the server according to a specific algorithm ：

• The first i individual （ from 0 Start index ） Request arrival
• If all servers are busy , The request will be discarded （ Not at all ）
• If the first (i % k) Servers available , Then assign the request to the server
• otherwise , Assign the request to the next available server （ Wrap around the list of servers and, if necessary, from 0 Start ）, for example , If the first i Server busy , Then try to assign the request to the (i+1) Servers , And then there's the (i+2) Servers , And so on .

Given a strictly increasing array of positive integers arrival , among arrival[i] It means the first one i The arrival time of a request , And another array load , among load[i] It means the first one i Load of requests （ Time required to complete ）. The goal is to find the busiest server . If the server successfully processes the most requests of all servers , The server is considered the busiest . Returns the containing the busiest server ID A list of . You can return in any order ID.

The topics are complicated , But after understanding, it is also relatively simple , The main idea of the solution is to maintain two lists , One is the list of idle servers free , The other is the list of servers that are executing the request buzy , Every time you get a new request , If free It's empty , Discard the request , If it is not empty, start from the (i % k) Look back for idle servers among servers , If not, start from 0 Start looking for idle servers .

There are two key points to note , One is initialization free and buzy Choose the class that can be sorted automatically , The other is in free It's best to have built-in functions when looking for idle servers in , If not, use dichotomy to find , If these two steps are not handled well, it is easy to timeout , My code is also just over , Time consuming is still 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 code 

Running results

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

Original link ：leetcode.com/problems/fi…

Your support is my greatest motivation