Calculate minimum number of students to go to series of lectures

Question

Some students wants to minimize their lecture attendance by sending minimum number of students to each of n lectures.

• Lecture i begins at time a[i] and ends at time b[i]
• It requires r[i][j] time to commute from lecture i to lecture j

Is there any algorithm to calculate the minimum number of students needed to attend all lectures?

Answer 1

Consider the classes as nodes in a graph. Construct edges between pairs of nodes (i,j) in the graph if it is possible to commute from lecture i to lecture j in time. The "root" nodes of your graph are the first classes of the day (classes that start before any other classes end in time to get to that class).

The first key observation is that the graph is directed and acyclic (you can't go back in time).

Your goal is to find the minimum number of paths through the graph such that every node is visited at least once. This immediately leads to the second key observation, which is that this can be accomplished greedily.

So the algorithm goes as follows:

1. Find the longest path in the directed acyclic graph (DAG)
2. Remove the nodes found in that path from the graph
3. Increment minNumStudents
4. Repeat until graph has no more nodes

Finding the longest path in a DAG is simple using dynamic programming:

1. Compute a topological order ordering of the graph
2. Keep an array dist with V elements (the number of nodes in the graph), initialized to 0
3. Keep an array prev with V elements, storing the previous node in the path

Then

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

Your longest path ends at the W such that dist[W] is maximum. And the longest path can be computed by backtracking from W using the prev array.