如何将O(N²)优化为O(NlogN)？多执行器任务调度问题求助

核心思路 #

放弃逐秒模拟的思路，采用事件驱动模型：只处理「执行器空闲」和「任务到达」两类关键事件，所有事件按时间排序后依次处理，直接跳过无操作的等待时段，从根源避免O(N²)的时间复杂度退化。

预处理与数据结构准备 #

1. 任务分组排序

   • 将所有任务按所属队列分组，每个队列内的任务按到达时间升序排列，同时为每个队列维护一个指针，标记当前待处理的队首任务。
   • 收集所有任务的到达事件，每个事件包含「到达时间」和「队列编号」，将所有到达事件按时间升序排序（时间相同时队列编号小的优先）。

2. 关键数据结构

   • 执行器最小堆：存储执行器的「空闲时间」和「编号」，排序规则为「空闲时间升序，空闲时间相同时编号升序」，用于快速获取最早可用且编号最小的执行器。
   • 队列候选堆：实现「最久未被选中队列优先」的逻辑，存储队列的「上次选中时间戳」和「队列编号」，排序规则为「时间戳升序」（时间戳越小代表越久未被选中）。仅允许有已到达队首任务的队列加入此堆。
   • 全局时间戳：每次队列被选中时递增，用于标记队列的选中顺序，确保候选堆的排序逻辑正确。
   • 队列就绪标记数组：记录队列是否已加入候选堆，避免重复入堆。

事件处理流程 #

1. 初始化

   • 将所有执行器初始化为空闲状态（空闲时间为0），加入执行器堆。
   • 将所有预处理好的任务到达事件加入事件队列（事件队列按时间升序排列）。
   • 初始化全局时间戳为0，队列就绪标记数组全为False。

2. 循环处理事件

   • 每次从事件队列取出时间最早的事件，分两类处理：
     • 任务到达事件：
       1. 若当前队列未加入候选堆，将其（当前时间戳，队列编号）加入候选堆，标记队列就绪，随后全局时间戳+1。
       2. 尝试批量分配任务：只要执行器堆和候选堆都不为空，就重复以下操作：
          • 弹出执行器堆顶的执行器（最早可用、编号最小）。
          • 弹出候选堆顶的队列（最久未被选中）。
          • 取出该队列的队首任务，计算任务开始处理时间为max(执行器空闲时间, 任务到达时间)。
          • 记录该任务对应的执行器编号和开始处理时间。
          • 更新执行器的空闲时间为开始处理时间 + 任务处理时长，将执行器重新加入执行器堆。
          • 队列指针后移，若队列还有未处理任务，将其重新加入候选堆（更新时间戳并标记就绪）。
     • 执行器空闲事件：
       1. 若候选堆不为空，直接执行上述任务分配流程；若候选堆为空，无需额外操作，等待下一个事件（即下一个任务到达事件）即可。

时间复杂度验证 #

• 事件队列的总规模为O(c + a)（c个任务到达事件，a个执行器空闲事件）。
• 每个事件处理过程中，堆操作的时间复杂度为O(loga + logb)：执行器堆操作是O(loga)，候选堆操作是O(logb)。
• 总时间复杂度为O((c + a) * log(max(a,b)))，完全满足O(NlogN)的要求，能在10秒内处理规模达10^5的输入。

内容的提问来源于stack exchange，提问作者Daniel Richter