current position:Home>leetcode 1606. Find Servers That Handled Most Number of Requests(python)
leetcode 1606. Find Servers That Handled Most Number of Requests(python)
2022-02-01 08:09:48 【Wang Daya】
「 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 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.
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
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202010809464446.html
The sidebar is recommended
- Python * * packaging and unpacking details
- Python realizes weather query function
- Python from 0 to 1 (day 12) - Python data application 2 (STR function)
- Python from 0 to 1 (day 13) - Python data application 3
- Numpy common operations of Python data analysis series Chapter 8
- How to implement mockserver [Python version]
- Van * Python! Write an article and publish the script on multiple platforms
- Python data analysis - file reading
- Python data De duplication and missing value processing
- Python office automation - play with browser
guess what you like
-
Python series tutorial 127 -- Reference vs copy
-
Control flow in Python: break and continue
-
Teach you how to extract tables in PDF with Python
-
leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal(python)
-
leetcode 1338. Reduce Array Size to The Half(python)
-
Object oriented and exception handling in Python
-
How to configure load balancing for Django service
-
How to embed Python in go
-
Python Matplotlib drawing graphics
-
Python object-oriented programming 05: concluding summary of classes and objects
Random recommended
- Python from 0 to 1 (day 14) - Python conditional judgment 1
- Several very interesting modules in Python
- How IOS developers learn Python Programming 15 - object oriented programming 1
- Daily python, Chapter 20, exception handling
- Understand the basis of Python collaboration in a few minutes
- [centos7] how to install and use Python under Linux
- leetcode 1130. Minimum Cost Tree From Leaf Values(python)
- leetcode 1433. Check If a String Can Break Another String(python)
- Python Matplotlib drawing 3D graphics
- Talk about deep and shallow copying in Python
- Python crawler series - network requests
- Python thread 01 understanding thread
- Analysis of earthquake distribution in the past 10 years with Python~
- You need to master these before learning Python crawlers
- After the old friend (R & D post) was laid off, I wanted to join the snack bar. I collected some data in Python. It's more or less a intention
- Python uses redis
- Python crawler - ETF fund acquisition
- Detailed tutorial on Python operation Tencent object storage (COS)
- [Python] comparison of list, tuple, array and bidirectional queue methods
- Go Python 3 usage and pit Prevention Guide
- Python logging log error and exception exception callback method
- Learn Python quickly and take a shortcut~
- Python from 0 to 1 (day 15) - Python conditional judgment 2
- Python crawler actual combat, requests module, python to capture headlines and take beautiful pictures
- The whole activity collected 8 proxy IP sites to pave the way for the python proxy pool, and the 15th of 120 crawlers
- Why can't list be used as dictionary key value in Python
- Python from 0 to 1 (day 16) - Python conditional judgment 3
- What is the python programming language?
- Python crawler reverse webpack, a real estate management platform login password parameter encryption logic
- Python crawler reverse, a college entrance examination volunteer filling platform encrypts the parameter signsafe and decrypts the returned results
- Python simulated Login, selenium module, python identification graphic verification code to realize automatic login
- Python -- datetime (timedelta class)
- Python's five strange skills will bring you a sense of enrichment in mastering efficient programming skills
- [Python] comparison of dictionary dict, defaultdict and orderdict
- Test driven development using Django
- Face recognition practice: face recognition using Python opencv and deep learning
- leetcode 1610. Maximum Number of Visible Points(python)
- Python thread 03 thread synchronization
- Introduction and internal principles of Python's widely used concurrent processing Library Futures
- Python - progress bar artifact tqdm usage