Расписание праздничных мероприятий

Question

Я работаю над расписанием в школьных целях. Я получаю упорядоченный по времени список событий, и моя цель - нарисовать их на временной шкале. Проблема в том, что какое-то событие перекрывает другое (как показано на рисунке ниже). Я хочу сделать это, чтобы «упаковать» эти события в самое маленькое возможное место. This is single day with overlapping events.

Первая фотография показывает, что мне удалось сделать до сих пор. Как видно на рисунке, прямоугольники не пересекаются друг с другом и прекрасно заполняют свободное пространство. НО мне не удалось найти разумный алгоритм для заказа. Second picture shows how events should be ordered.

Это два условия, которые делают эту проблему отличается от классической задачи упаковки:

1. События дал координаты х (определенные начало и конец).
2. События имеют фиксированную ширину, высота произвола.

Answer 1

Эта проблема напоминает мне о проблеме фрагментации файловой системы. Простыми решениями было бы реализовать один из известных алгоритмов, например. сперва или лучше всего подходит.

Но я думаю, вы хотите лучшее решение. Вот почему я предлагаю реализовать backtracking algorithm. Имейте в виду, что я могу вызвать длительные промежутки времени, но я думаю, что это не имеет особого значения в вашем контексте.