Leetcode#1822-使用服务器处理任务
/ 4 min read
Table of Contents
读题
这种模拟题读题是最麻烦的，题目是按tasks的顺序给servers分配任务，给servers分配任务时，选择最小weight且空闲的servers
需要注意的是，任务解锁的时候才能分配给服务器，当t=0时，第0件任务解锁，当t=1时，第1件任务解锁。
答案是，每个tasks分配给那个服务器。
思路
看一眼标签知道是用优先队列，不过按题目，每次取最小Weight, 其实就能想到小根堆/优先队列了，即当前可用服务器用优先队列表示。 若Weight有一样的，索引最小，那么我们也要把索引给作为比较条件。
这个其实就涉及到两个操作，一个是取服务器，一个是释放服务器。
拿Task的时候，可以将servers列表直接堆化，然后依次取就好，重要的是怎么表示服务器的占用和释放？
初步思路
初步的思路是，time是一个全局时间，我可以初始化一个数组，在取用哪个服务器的时候，将时间置为当前时间+任务时间，然后释放的时候，判断占用截至时间是否和当前时间一致，若是则直接扔到优先队列里。
优化版本
这样看似合理，但是释放的时候引入了循环，但是细想一下，释放的时候，不也是每次取最小的结束时间，然后和当前时间比？
所以表示占用的队列也可以变成优先队列，每次塞入(占用截至时间, idx)就好了。
特别考虑
如果服务器都在占用呢？ 那么我可以直接当前time等于堆顶，即最小的占用截至时间，用来省略一些无意义的循环。
考虑任务解锁这个情况？ time其实就相当于一个指针，指明了从0到time这个idx之间哪些任务是解锁的，所以一个时刻是可以放入多个任务的。
实现
代码写的有点丑，凑活看吧
import heapq
class Solution: def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]: pq, pq_busy, ans = [],[],[] for k, v in enumerate(servers): heapq.heappush(pq, (v, k)) time, pt = 0,0 while pt < len(tasks): # 放回server Go = False while not Go and len(pq_busy)!=0: t, idx = pq_busy[0] if t == time: heapq.heappop(pq_busy) heapq.heappush(pq, (servers[idx],idx)) else: Go = True # 取server while len(pq) !=0 and (time - pt + 1) >0 and pt < len(tasks): weight, idx = heapq.heappop(pq) heapq.heappush(pq_busy, (time + tasks[pt], idx)) ans.append(idx) pt += 1 # 处理时间 time = time + 1 if len(pq_busy)!=len(servers) else pq_busy[0][0] return ans