Алгоритм для упаковки временных интервалов

Question

У меня есть набор событий со временем начала и окончания. Я хочу, чтобы сделать их как длинные коробки в серии строк, не перекрываются, что-то вроде этого

00:00 01:00 02:00 03:00 04:00 05:00 06:00 07:00 08:00 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 
     AAAAAAAAAAAA BBBBBB  CCCCCCCCCCCCCCCCCCCC  DDDDDDDDDDDD 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 
     EEEEEEEEEEEEEE  FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 
      GGGGGGGGGGGGGGGGGGG   HHHHHHHH  IIIIIIIIIIIII 
--|--------|--------|--------|--------|--------|--------|--------|--------|-- 

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

Есть ли для этого известный алгоритм?

Answer 1

В Международном конкурсе по расписанию 2007 года был составлен график составления расписания трека и экзамена. Многие исследователи участвовали в конкурсе . Много эвристики и метаэвристик были испробованы, но в конце местных метаэвристики поиска (такие как Табу Поиск и смоделированного Отжиг) четко бить другие алгоритмы (например, генетические алгоритмы).

Взгляните на 2 рамки с открытым исходным кодом, используемых некоторыми из финалистов:

JBoss OptaPlanner (Java, с открытым исходным кодом) Unitime (Java, с открытым исходным кодом) - более для вузов

- Джеффри Де Смет: Algorithm for creating a school timetable

Ссылка:

• http://en.wikipedia.org/wiki/Simulated_annealing
• http://en.wikipedia.org/wiki/Tabu_search

Answer 2

Я просто собирал их с жадностью (перейдите слева направо и добавьте событие на первый трек в направлении сверху вниз, где он подходит). Это быстро и детерминировано и, скорее всего, на практике дает хорошие результаты.

Answer 3

Я решил идентичную проблему следующим раствором:

1. Найти LB = мин (начальное время) и RB = макс (Конечное время).
2. Добавить пустую строку с длиной LB в RB;
3. Для каждого сектора «свободное время» в строке (изначально будет только один сектор: LB в РБ):
   • 3,1 Найти самый длинный элемент, который будет соответствовать в этом секторе;
   • 3.2.1 Если есть такой элемент - вставлять в строку;
   • 3.2.2 В противном случае очевидно, что этот свободный сектор непригоден;
4. Если есть еще элементы, оставшиеся после всех текущих свободных секторов были протестированы, перейти к этапу 2.

Имейте в виду, что при вставке элемента (этап 3.2.1), множество свободных сектора, которые перечислены (шаг 3), будут меняться.

Answer 4

Это известно как Interval Partitioning. Жадный алгоритм, который назначает поля в порядке времени запуска и помещает ящик в первую строку, где он подходит (или открывает новую строку, если он нигде не подходит) дает оптимальный результат. См. Например, Kleinberg & Tardos: «Дизайн алгоритмов».

Answer 5

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

1. Узнайте, какие даты накладываются друг на друга. Возможно, на карте, где вы сопоставляете каждую запись со списком записей, которые накладываются на нее.
2. Сортировка элемента к этому времени начала.
3. До тех пор, пока в одной строке есть место, выделите элемент с элементом с самым близким временем начала до конца последнего элемента.
4. Из всех элементов, которые пересекаются с этим, выберите тот, который имеет наибольшее перекрытие, которое не перекрывается с предыдущим и добавляет его в вашу строку.
5. Если строка заполнена, проверьте самый большой зазор и посмотрите, входит ли элемент в нее; иначе перейдите к следующей строке.

Возможно, взвешивание элементов путем перекрытия и эта окончательная проверка на шаге 5 могут помочь улучшить нормальный жадный подход.