ЯсноПонятно24

Для решения данной задачи можно воспользоваться методом жадного выбора. Необходимо отсортировать заявки лекторов по времени окончания лекции. Затем пройти по отсортированному списку и помещать лекторов в аудитории, если время начала их лекции не пересекается с временем окончания лекции другого лектора в той же аудитории.

Таким образом, минимальное количество лекторов, которым не придется отказать, чтобы в каждой аудитории всегда работал не более одного преподавателя, будет равно количеству аудиторий.

Пример:

Пусть у нас есть следующие заявки лекторов:

Лектор 1: начало - 9:00, конец - 10:00 Лектор 2: начало - 9:30, конец - 10:30 Лектор 3: начало - 10:00, конец - 11:00

Отсортируем их по времени окончания лекции:

Лектор 1: начало - 9:00, конец - 10:00 Лектор 2: начало - 9:30, конец - 10:30 Лектор 3: начало - 10:00, конец - 11:00

Пройдем по отсортированному списку:

1. Лектор 1 занимает аудиторию с 9:00 до 10:00
2. Лектор 2 не может занять аудиторию, так как пересекается с Лектором 1
3. Лектор 3 занимает аудиторию с 10:00 до 11:00

Таким образом, минимальное количество лекторов, которым не придется отказать, чтобы в каждой аудитории всегда работал не более одного преподавателя, равно 2.