Рассчитайте минимальное количество студентов, чтобы пойти на серию лекций

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. Вычислить топологический порядок ordering графика
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] является максимальным.И самый длинный путь может быть вычислен путем возврата от W с использованием массива prev.