Алгоритм суммирования событий / предметов

Question

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

               M T W R F S U M T W R F S U M T W R F S U
Category 1:   |Event 1|     |Event 2| |------Event 3--|
                |---------Event 4-----------| |-Event 5-|

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

Для любопытных я смотрю, как обойти ограничения представления календаря Ганта в SharePoint 2007. Нашим пользователям нравится это представление, но они не хотят, чтобы одна задача в строке.

Answer 1

Моей первой попыткой будет сортировка задач по времени / дате начала. Затем я бы поместил их по очереди в первую строку, на которой их время начала еще не было занято. Я (совсем) не уверен, что это дает оптимальные результаты (то есть всегда использует наименьшее количество возможных строк), но это должно быть хотя бы наполовину разумно.

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

Редактировать: просто для ясности: здесь я предполагаю, что вопрос касается только отображения графика событий, для которых время начала и продолжительность уже известны, поэтому оптимизация просто означает отображение данных максимально "компактно". Я не говорю о попытке создать само расписание (т. Е. Пытаться выяснить, какие события планировать, когда). В зависимости от задействованных ограничений, это обычно гораздо более сложная проблема. Это довольно легко, если ваши единственные ограничения - это зависимости между задачами, но когда вы добавляете такие вещи, как максимальное использование рабочей силы и ограниченные ресурсы (например, задача X может выполняться только человеком A, B или C, задача Y - B , C или D и т. Д.), Ситуация становится намного более сложной очень быстро.