根据军衔查找士兵完成的任务

引言

有效的资源分配对于优化任务分配以最大化生产力至关重要。在根据军衔分配士兵以及任务在不同时间进入系统的情况下，需要一种战略性方法。目标是，在给定一个包含士兵军衔的数组和一个表示每个任务所需时间的数组的情况下，优化任务分配过程。士兵必须根据其军衔被分配任务；若军衔相同，则选择索引最小的士兵来打破僵局。最终目标是返回一个包含分配给每个任务的士兵索引的数组。

方法概述

通过将士兵的军衔和索引保存在一个优先队列（或最小堆）中，可以有效地解决这个问题。为了进一步跟踪每个士兵何时可用，使用了一个数组。该算法反复遍历任务，在每个时间步确定是否有士兵可用并相应地分配任务。

代码

输出

代码解释

类定义

• 代码中定义的类名为 TaskAssignmentOptimizer。

方法签名

• 该类中有一个公共静态方法，名为 assignTasks。它接受两个参数：一个表示士兵军衔的整数列表 (ranks) 和一个表示完成每个任务所需时间的整数列表 (tasks)。
• 该方法返回一个整数列表，表示分配给每个任务的士兵的索引。

优先队列的初始化

• 士兵根据其军衔被安排在一个名为 pq 的 PriorityQueue 中。优先级由军衔和原始索引共同决定。
• 根据优先队列中使用的比较器，军衔较低的士兵被赋予优先权。如果军衔出现平级，则优先考虑索引较低的士兵。

数据结构的初始化

• 已分配的任务最初存储在一个名为 ans 的 ArrayList 中。
• 一个名为 free 的哈希映射被初始化，用于跟踪不同时间点的空闲士兵。
• 一个名为 timer 的整型变量被初始化，用于跟踪当前时间。

用士兵信息初始化优先队列

• 代码在遍历士兵军衔 (ranks) 后，将每个士兵及其军衔和索引添加到优先队列 (pq) 中。

任务分配的主循环

• 为了遍历任务，代码进入一个循环。
• 在循环内部，此时已完成任务的士兵被释放。这些士兵从 free 映射中移除后，被返回到优先队列中。
• 接下来，当前时间 (timer) 的条目从 free 映射中移除。

验证士兵的可用性

• 如果当前没有可用的士兵，这意味着优先队列 (pq) 为空。
• 在这些情况下，代码会检查 free 映射中的键，以确定士兵最早何时变为空闲，然后相应地修改计时器。为了重新评估当前任务，它还会减少循环索引 (i)。

任务分配

• 如果优先队列中有可用的士兵，代码会弹出顶部的士兵，并将相关的任务分配给该士兵。
• ans 列表会用分配的士兵的索引进行更新。
• 一旦士兵完成了当前任务，free 映射就会更新，以显示该士兵的下一个空闲时间。
• 为了进入下一个时间步，计时器会递增一。

时间和空间复杂度分析

时间复杂度

主循环内的操作要么是常数时间（对于优先队列操作），要么是对数时间（对于每个任务迭代）。因此，整体时间复杂度为 O(N log N)，其中 N 是 ranks 数组的大小。

空间复杂度

tasks 数组的大小为 M，ranks 数组的大小为 N。因此，空间复杂度为 O(M + N)。这考虑了诸如 free 映射、优先队列和额外变量等数据结构所需的空间量。