algorithm - 计算参加系列讲座的最少学生人数

Question

一些学生希望通过派出最少数量的学生参加每个 n 讲座来最大限度地减少他们的讲座出勤率。

• 讲座 i 开始时间 a[i] 结束时间 b[i]
• 从讲座 i 到讲座 j 需要 r[i][j] 时间

是否有任何算法可以计算出参加所有讲座所需的最少学生人数？

Answer 1

将类视为图中的节点。如果可以及时从讲座 i 到讲座 j，则在图中的节点对 (i,j) 之间构造边。图形的“根”节点是当天的第一个类(在任何其他类(class)结束之前开始的类(class)及时到达该类(class))。

第一个关键观察结果是该图是有向的和非循环的(您不能及时返回)。

您的目标是找到通过图形的最少路径数，以使每个节点至少被访问一次。这立即导致第二个关键观察结果，即这可以贪婪地完成。

所以算法如下:

1. 在有向无环图 (DAG) 中找到最长路径
2. 从图中删除在该路径中找到的节点
3. 增加 minNumStudents
4. 重复直到图没有更多节点

使用动态规划在 DAG 中查找最长路径很简单:

1. 计算一个topological order图的顺序
2. 保存一个数组dist，包含V个元素(图中的节点数)，初始化为0
3. 保存一个数组prev，包含V元素，存储路径中的前一个节点

然后

for each vertex `V` in `ordering`
    for each edge (V,W)
        dist[W] = min(dist[W],dist[V]+1)
        prev[W] = V;

您最长的路径在 W 处结束，因此 dist[W] 是最大的。最长的路径可以通过使用 prev 数组从 W 回溯来计算。