LC 1882. 使用服务器处理任务

https://leetcode-cn.com/problems/process-tasks-using-servers/

好几次遇到这类问题了，我觉得基本上可以抽取出某种模式了：

  1. server available可以作为单独事件来看待，同样task available也可以
  2. 所有事件都放在优先队列里面，按照时间进行排序
  3. 从优先队列里面取出第一个元素，这个元素的时间就是 current_timestamp.
  4. 然后从优先队列里面取出所有的相同时间的事件，这些事件都可以进行处理
  5. 处理这些事件（匹配或者是什么），然后会产生新的事件（server available next time）
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        import heapq
        ev = []

        for i in range(len(servers)):
            ev.append((0, 0, i))

        for i in range(len(tasks)):
            ev.append((i, 1, i))

        heapq.heapify(ev)

        from collections import deque
        srv = []
        Q = deque()

        ans = [-1] * len(tasks)
        todo = len(tasks)

        while ev and todo:
            # print('ev', ev)
            ct = ev[0][0]

            while ev and ev[0][0] == ct:
                (t, type, idx) = heapq.heappop(ev)
                if type == 0:
                    # server avail
                    heapq.heappush(srv, (servers[idx], idx))
                elif type == 1:
                    # task avail
                    Q.append(idx)

            # print(srv, Q)
            while Q and srv:
                _, srvidx = heapq.heappop(srv)
                tidx = Q.popleft()
                ans[tidx] = srvidx
                print('assign ', tidx, srvidx)
                todo -= 1
                heapq.heappush(ev, (ct + tasks[tidx], 0, srvidx))
        return ans