<p>You are given two <strong>0-indexed</strong> integer arrays <code>servers</code> and <code>tasks</code> of lengths <code>n</code>​​​​​​ and <code>m</code>​​​​​​ respectively. <code>servers[i]</code> is the <strong>weight</strong> of the <code>i<sup>​​​​​​th</sup></code>​​​​ server, and <code>tasks[j]</code> is the <strong>time needed</strong> to process the <code>j<sup>​​​​​​th</sup></code>​​​​ task <strong>in seconds</strong>.</p>

<p>Tasks are assigned to the servers using a <strong>task queue</strong>. Initially, all servers are free, and the queue is <strong>empty</strong>.</p>

<p>At second <code>j</code>, the <code>j<sup>th</sup></code> task is <strong>inserted</strong> into the queue (starting with the <code>0<sup>th</sup></code> task being inserted at second <code>0</code>). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the <strong>smallest weight</strong>, and in case of a tie, it is assigned to a free server with the <strong>smallest index</strong>.</p>

<p>If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned <strong>in order of insertion</strong> following the weight and index priorities above.</p>

<p>A server that is assigned task <code>j</code> at second <code>t</code> will be free again at second <code>t + tasks[j]</code>.</p>

<p>Build an array <code>ans</code>​​​​ of length <code>m</code>, where <code>ans[j]</code> is the <strong>index</strong> of the server the <code>j<sup>​​​​​​th</sup></code> task will be assigned to.</p>

<p>Return <em>the array </em><code>ans</code>​​​​.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> servers = [3,3,2], tasks = [1,2,3,2,1,2]
<strong>Output:</strong> [2,2,0,2,1,2]
<strong>Explanation: </strong>Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
<strong>Output:</strong> [1,4,1,4,1,3,2]
<strong>Explanation: </strong>Events in chronological order go as follows: 
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. 
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. 
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>servers.length == n</code></li>
	<li><code>tasks.length == m</code></li>
	<li><code>1 &lt;= n, m &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>1 &lt;= servers[i], tasks[j] &lt;= 2 * 10<sup>5</sup></code></li>
</ul>

'''
算法原理
维护两个优先队列：

cpu：存储当前空闲的服务器，用一个最小堆来按权重排序。如果权重相同，则按服务器的索引排序。
busy：存储当前忙碌的服务器，按服务器变为空闲的时间排序。
初始化服务器列表：

通过遍历 servers 列表，将每个服务器的权重和索引加入 cpu 优先队列。
任务分配循环：

对于每个任务，从时间 time 开始，算法检查是否有服务器在该时间点变为空闲状态。
如果有，算法将这些服务器从 busy 队列中移除，并将它们重新放回 cpu 队列中。
如果在当前时间点没有空闲服务器，则时间 time 会跳到 busy 队列中最早有服务器变为空闲的时间点。
然后从 cpu 中取出权重最小且索引最小的服务器，将任务分配给该服务器，并更新 busy 队列，记录该服务器的空闲时间。
返回结果：

结果数组 ans 中保存了每个任务对应的服务器索引。

算法的时间复杂度
设 n 为任务的数量，m 为服务器的数量。
初始化时将服务器压入堆的时间复杂度为 O(mlogm)。
任务分配循环中，每次任务分配都涉及堆的插入和删除操作，时间复杂度为 O(logm)，因此总体复杂度为 O(nlogm)。
因此，整个算法的时间复杂度为 O((n+m)logm)。这个复杂度在服务器和任务数量较大的情况下依然能够高效处理。
'''
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        import heapq
        
        # 获取任务数量
        n = len(tasks)
        # 初始化答案数组，初始值为-1
        ans = [-1 for _ in range(n)]

        time = 0  # 当前时间
        cpu = []  # 存储空闲服务器的最小堆，格式为 [权重, 服务器索引]
        busy = [] # 存储忙碌服务器的最小堆，格式为 [空闲时间, 服务器索引]

        # 初始化空闲服务器堆
        for i, v in enumerate(servers):
            heapq.heappush(cpu, [v, i])

        i = 0
        while i < n:
            # 确保当前时间至少为任务的到达时间
            time = max(time, i)
            
            # 释放在当前时间或之前的空闲服务器
            while busy and busy[0][0] <= time:
                free_time, cpu_ind = heapq.heappop(busy)
                # 将释放的服务器重新加入空闲服务器堆
                heapq.heappush(cpu, [servers[cpu_ind], cpu_ind])
            
            # 如果没有空闲服务器，跳到最近的服务器变空闲的时间
            if not cpu:
                time = busy[0][0]
                while busy and busy[0][0] <= time:
                    free_time, cpu_ind = heapq.heappop(busy)
                    heapq.heappush(cpu, [servers[cpu_ind], cpu_ind])
            
            # 从空闲服务器堆中取出最优服务器
            cpu_weight, cpu_ind = heapq.heappop(cpu)
            # 将该服务器标记为忙碌，并记录其空闲时间
            heapq.heappush(busy, [time + tasks[i], cpu_ind])
            # 记录任务分配的服务器索引
            ans[i] = cpu_ind
            i += 1

        return ans

1576