根据持续时间和可能的时间段查找活动时间表

Question

我正在尝试查找或想知道您是否知道可用于特定事件调度任务的算法：

给定一个事件列表

e

，长度为

Ne

，其中每个事件有：

• 持续时间

  d

  （以分钟为单位）
• 可能的时间段列表

  t

  （日期/时间），长度为

  Nt

  （通常为1-3）

为每个每个事件提供一个可能的一个时间段列表，以便时间段之间的时间最大化

只是想稍微思考一下，我认为这可能需要与

创建学校时间表类似的方法，但对此缺乏经验，我不确定我的具体限制是否会发生很大变化

Answer 1

由于每个活动的时段很少，您可以搜索，例如对没有事件发生冲突的比赛进行回溯。由于每个事件的时间段很少，搜索空间的分支并没有那么严重。

优化：如果您期望多个可能的时间段不会与其他事件的任何其他可能的时间段发生冲突，您可以将这些事件放在前面，只搜索其余的事件。

优化：从时隙数最少的事件开始，时隙数相同的事件从持续时间最长的事件开始。这应该会导致早期碰撞，从而减少搜索空间。