計算參加系列講座的學生的最低人數

Question

有些學生希望通過向每個n講座發送最少的學生人數來儘量減少他們的講座出席率。

• 講座i開始於時間a[i]和時間結束b[i]
• 它需要r[i][j]時間從講座i通勤講學j

是否有任何的算法來計算所需要的學生的最小數量參加所有講座？

Answer 1

將類視爲圖中的節點。如果可以及時從講座i到講座j，則在圖中的節點對(i,j)之間構建邊緣。圖的「根」節點是當天的第一類（在任何其他類到達該類之前結束的類）。

第一個關鍵的觀察是該圖是有向和無環的（你不能回到過去）。

您的目標是找到通過圖的路徑的最小數量，以便每個節點至少訪問一次。這立即導致了第二個關鍵的觀察，這是可以貪婪地完成的。

所以算法進行如下：

1. 發現在向無環圖的最長路徑（DAG）
2. 取下圖
3. 增量minNumStudents
4. 在路徑中找到的節點重複直到圖形沒有更多節點

查找DAG中最長的路徑很簡單納克動態規劃：

1. 計算圖表
2. 保持陣列的topological orderorderingdist與V元素（節點的圖中的編號），初始化爲0
3. 保持陣列prev與V元件，將前一個節點存儲在路徑中

Then

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回溯來計算。