基于多因素的事件规划算法和数据结构建议

Question

我一直在努力寻找正确的算法和数据结构来规划给定天数的事件。这些事件有多个与之关联的数据点。我需要一个人在给定的日子里可以做的最多的事件。

事件的数据点:

1. 执行事件所需的时间
2. 事件可以完成的时间范围(例如上午 9 点至下午 5 点)
3. 事件彼此接近(例如，事件 1 可以在 A 点，事件 2 最好应该靠近它，依此类推)
4. 评分最高的事件应该首先完成

我看了activity selection algorithm但不确定这是否不适合我正在查看的内容。

Answer 1

设 G(V, E) 是按这种方式定义的有向无环图 (DAG):

• 每个事件在V中有一个顶点v
• V中还有两个特殊的顶点v_start和v_target
• 在 E 中对于每对事件 i 和 j 都有一条边 (i, j)这样 i 在 j 之前结束并且根据您的接近标准“兼容”
• 对于 V 中不同于 v_start 和 v_end 的每个顶点，边 (v_start, v) 和 (v, v_end) 都在 E 中(即 v_start 对每个事件都有一个传出边，v_end 对于每个事件都有一个传入边)

然后你想要的是从源到目的地的最长路径，这可以通过遵循概述的简单算法在线性时间内完成 here .