Расписание занятий по графическому алгоритму

Question

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

Университет пытается запланировать n разных классов. У каждого класса есть время начала и окончания. Все занятия должны преподаваться в пятницу. Есть только два класса.

Помогите университету решить, можно ли планировать эти классы без какого-либо конфликта времени (т. Е. Два класса с перекрывающимися классами времени запланированы в одном классе).

Answer 1

Сортируйте классы по времени запуска (O (nlogn)), затем выполните их в порядке (O (n)), отметив время начала и окончания и ищите случай более двух классов, проходящих в то же время время.

Answer 2

Это не проблема с двудольным графическим решением. Кто вам сказал?

@Beta почти правильно. Создайте список пар <START, time> и <END, time>. Каждый класс имеет две пары в списке, один START и один END.

Теперь отсортируйте список по времени. Или, если хотите, поместите их в кучу минут, что составляет до heapsort. Для равных времен поставьте END в тройку перед началом действия. Затем выполните следующий цикл:

set N = 0 
while sorted list not empty 
    pop <tag, time> from the head of the list 
    if tag == START 
    N = N + 1 
    if N > 2 return "can't schedule" 
    else // tag == END 
    N = N - 1 
    end 
end 
return "can schedule" 

Вы можете легко обогащать алгоритма немного вернуть периоды времени, когда более 2-х классов находятся в сессии в то же время, вернуть эти классы, и другая полезная информация.

Answer 3

Это действительно двунаправленная/двухцветная проблема.

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

Графа вы создали, если он может быть двухцветными, то каждый «черный» узел будет принадлежать и каждый комнате 1 «белому» узел будет принадлежать room2