Интервальная перегородка, другой подход - устраивать лекции в минимальном количестве аудиторий

Question

Проблема планирования лекций в минимальном количестве классных комнат заключается в следующем: найдите минимальное количество классных комнат, чтобы запланировать все лекции так, чтобы в одной и той же комнате не было двух одновременно.

Общий алгоритм, которыйЯ нахожу в книгах:

Sort intervals by starting time so that s1 ≤ s2 ≤ ... ≤ sn.
d ← 0 //number of classrooms
for j = 1 to n {
 if (lecture j is compatible with some classroom k)
 schedule lecture j in classroom k
 else
 allocate a new classroom d + 1
 schedule lecture j in classroom d + 1
 d ← d + 1
}

Теперь я думал о альтернативном подходе, где я сортирую свои лекции, заканчивая время в порядке возрастания, и каждый раз проверяю, совместима ли лекция j с некоторым классом k иЕсть несколько классных комнат, которые совместимы с этой лекцией, я планирую это в классной комнате, время окончания последних работ в которой ближе всего к началу работы, то есть минимизирует время, когда класс пуст.

Sort intervals by starting time so that f1 ≤ f2 ≤ ... ≤ fn.
d ← 0 //number of classrooms
for j = 1 to n {
 if (lecture j is compatible with some classroom k)
 schedule lecture j in classroom k which was used last
 else
 allocate a new classroom d + 1
 schedule lecture j in classroom d + 1
 d ← d + 1
}

Я хотел бы знать, является ли этот подход правильным (не обязательно оптимальным). Я выполнил тест на пару случаев, и, похоже, все будет в порядке. Если да, как я могу доказать его правильность? Если нет, то как я могу изменить алгоритм?

Answer 1

Да, это будет работать.
Вы должны поддерживать массив End [], который может сообщить вам время последнего урока в классе.
Итак, запускайте цикл над вашим отсортированным массивом и для каждой лекции посещайте всеклассные комнаты уже инициализированы. Если у вас есть класс, в котором End [идентификатор класса]
Другой способ:

, если вы знаете минимальное время начала и максимальное время окончания всех лекций независимо. Затем вы должны запустить цикл от минимального начального времени до максимального конечного времени и подсчитать, сколько лекций проводится за текущее время. максимальное количество среди всех я (минимальное время <= i <= максимальное время) ваш ответ. </p>