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

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

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

 bbb
aa cc

или же

aa cc
 bbb

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

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

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

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