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

一些学生希望通过向每个n讲座发送最少数量的学生来最小化他们的演讲出席率。
讲座开始于时间i结束于时间a[i]
它需要b[i]时间从讲座r[i][j]到讲座i
有没有算法来计算所有课程所需的最少学生人数？

最佳答案

将类视为图中的节点。如果能够及时地从讲座(i,j)切换到讲座i，则在图中的成对节点j之间构造边。图的“根”节点是一天中的第一个类（在任何其他类到达该类之前开始的类）。
第一个关键的观察是图是有向的和无环的（你不能回到过去）。
您的目标是找到通过图的最小路径数，以便每个节点至少访问一次。这立即导致了第二个关键的观察，即这可以贪婪地完成。
算法如下：
在有向无环图（DAG）中寻找最长路径
从图中删除在该路径中找到的节点
增量minNumStudents
重复，直到图没有更多节点
使用动态编程查找DAG中的最长路径非常简单：
计算图形的atopological orderordering。
使用dist元素（图中的节点数）保持数组V，初始化为0
使用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]是最大的。最长路径可以通过使用W数组从prev进行回溯来计算。