О сложности построения непрерывного расписания из специального класса

Abstract

Рассматривается задача построения расписания, в котором каждый преподаватель должен провести занятия в последовательные часы. Показано, что если у преподавателя ровно 2, 4 или 6 уроков, оценка сложности алгоритма построения непрерывного расписания длительностью 6 зависит лишь от числа учебных групп n и имеет вид O(n2).

The problem of timetable construction when each teacher has lessons in consecutive hours is observed. It is shown that if a teacher has exactly 2, 4 or 6 lessons, then the complexity of timetable construction algorithm for timetable with duration 6 depends only on the number of classes n and is of the form O(n2).