Ищем алгоритм для эффективного размещения баннеров событий календаря.

Question

Я ищу алгоритм для эффективного размещения баннеров событий на весь день или несколько дней, очень похожих на просмотр месяца в Outlook или Календаре Google.У меня есть ряд событий с датой начала и окончания, упорядоченных по возрастанию даты начала (а затем окончания) (или в любом другом порядке, который вам нравится, я собираю события из таблицы базы данных).Я хотел бы свести к минимуму средний объем используемого вертикального пространства, потому что после баннеров событий мне нужно будет разместить другие события только для этого дня (они всегда идут после баннеров для определенной даты).Так, например, если бы у меня было два события, одно 10.01.11.11 и одно 11.01.15.11, я бы предпочел расположить их так (каждый столбец представляет собой один день):

 bbbbb
aa

и не так:

aa
 bbbbb

потому что, когда я добавляю события только за день (x, y и z), я могу сделать это (я бы предпочел первое, не хочу второе):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

Но это не так просто, как разместить более длинные события первыми, потому что с 1/10 по 1/11, 13/1/14 и 11/11 по 1/13 я бы хотел:

aa cc
 bbb

в отличие от:

 bbb
aa cc

потому что это позволит событиям x и y:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

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

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

Это трата много места на протяжении большей части дней мероприятий «е».

Есть идеи?

Answer 1

Вот общий эскиз одного из возможных решений (с использованием целых чисел дней недели вместо полноценных дат).Этот интерфейс:

public interface IEvent {

    public abstract int getFirst();  // first day of event
    public abstract int getLast();   // last day of event
    public abstract int getLength(); // total number of days
    public abstract char getLabel(); // one-char identifier

    // true if this and that have NO days in common
    public abstract boolean isCompatible(IEvent that);

    // true if this is is compatible with all events
    public abstract boolean isCompatibleWith(Collection<IEvent> events);

}

должен быть реализован для использования алгоритма, выраженного в layout метод ниже.

Кроме того, конкретный класс должен реализовать Comparable создать естественный порядок, в котором более длительные события предшествуют более коротким событиям.(В моем примере реализации для демонстрации ниже использовался порядок убывания длины, затем возрастающая дата начала, а затем возрастающая метка.)

А layout метод принимает коллекцию IEvent экземпляры и возвращает Map который присваивает каждой строке презентации набор событий, которые могут быть показаны в этой строке.

public Map<Integer,Set<IEvent>> layout(Collection<IEvent> events) {
    Set<IEvent> remainingEvents = new TreeSet<IEvent>(events);
    Map<Integer,Set<IEvent>> result = new TreeMap<Integer,Set<IEvent>>();
    int day = 0;
    while (0 < remainingEvents.size()) {
        Set<IEvent> dayEvents = new TreeSet<IEvent>();
        for(IEvent e : remainingEvents) {
            if (e.isCompatibleWith(dayEvents)) {
                dayEvents.add(e);
            }
        }
        remainingEvents.removeAll(dayEvents);
        result.put(day, dayEvents);
        ++day;
    }
    return result;
}

Каждая строка формируется путем выбора самого длительного оставшегося события и постепенного выбора всех дополнительных событий (в порядке, описанном выше), которые совместимы с ранее выбранными событиями для текущей строки.В результате все события «плывут» вверх, насколько это возможно, без столкновений.

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

Event collection:
    x(1):4
    b(5):2..6
    y(1):5
    a(2):1..2
    z(1):6
Result of layout:
    0 -> {b(5):2..6}
    1 -> {a(2):1..2, x(1):4, y(1):5, z(1):6}
Visual presentation:
      bbbbb
     aa xyz

Event collection:
    x(1):1
    b(3):2..4
    a(2):1..2
    c(2):4..5
    y(1):5
Result of layout:
    0 -> {b(3):2..4, x(1):1, y(1):5}
    1 -> {a(2):1..2, c(2):4..5}
Visual presentation:
     xbbby 
     aa cc 

Event collection:
    f(2):1..2
    h(2):1..2
    d(4):1..4
    e(4):2..5
    c(1):6
    a(2):5..6
    g(4):2..5
    b(2):0..1
Result of layout:
    0 -> {d(4):1..4, a(2):5..6}
    1 -> {e(4):2..5, b(2):0..1, c(1):6}
    2 -> {g(4):2..5}
    3 -> {f(2):1..2}
    4 -> {h(2):1..2}
Visual presentation:
     ddddaa
    bbeeeec
      gggg 
     ff    
     hh    

Answer 2

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

Например, организуйте данные в строки, которые вам нужны для определенного дня, и организуйте события наилучшим образом, начиная с самых длинных событий (не обязательно отображать их первыми, но их необходимо систематизировать). сначала) и переходим к самым коротким событиям.Это позволит вам соответствующим образом визуализировать выходные данные, не теряя места и избегая этих «е» дней событий.Дополнительно тогда:

 bbb
aa cc

или

aa cc
 bbb

не будет иметь значения, потому что x и y всегда можно пойти по обе стороны bbb или даже между aa и cc

Надеюсь, вы найдете это полезным.